bzoj 1112: [POI2008]砖块Klo【对顶堆】

priority_queue实现的对顶堆，细节超级多WA了十几次……但是理论上是最简便的orz其实是我已经不会写平衡树了

枚举左端点，显然要把这一段的高度搞成(l,l+k-1)的高度中位数，所以需要一个支持插入删除查询中位数的东西，我们使用对顶堆

然后关于删除，我们手动维护size和sum，删的时候直接减掉就行，然后堆里面放二元组高度和i，需要使用堆顶的时候，把i<l的pop掉就是可用堆顶了

注意q1最大值<=q2最小值，虽然判了但是还是会WA，在调整size的时候顺便判一下即可

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N=100005;

int n,m,a[N],bl[N];

long long sm1,sm2,si1,si2,mn,ansl,ansm;

struct qwe

{

    int v,id;

    qwe(int V=0,int ID=0)

    {

        v=V,id=ID;

    }

    bool operator < (const qwe &b) const

    {

        return v<b.v;

    }

};

struct ewq

{

    int v,id;

    ewq(int V=0,int ID=0)

    {

        v=V,id=ID;

    }

    bool operator < (const ewq &b) const

    {

        return v>b.v;

    }

};

priority_queue<qwe>q1;

priority_queue<ewq>q2;

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

void del(int i)

{

    while(!q1.empty()&&q1.top().id<i)

        q1.pop();

    while(!q2.empty()&&q2.top().id<i)

        q2.pop();

}

void tiao(int i)

{

    del(i);

    while(!q1.empty()&&!q2.empty()&&q1.top().v>q2.top().v)

    {

        del(i);

        si1--,si2++;

        sm1-=q1.top().v,sm2+=q1.top().v;

        q2.push(ewq(q1.top().v,q1.top().id)),q1.pop();

    }

    while(si1<si2)

    {

        del(i);

        si1++,si2--;

        sm1+=q2.top().v,sm2-=q2.top().v;

		bl[q2.top().id]=1;

        q1.push(qwe(q2.top().v,q2.top().id)),q2.pop();

    }

    while(si1-1>si2)

    {

        del(i);

        si1--,si2++;

        sm1-=q1.top().v,sm2+=q1.top().v;

		bl[q1.top().id]=2;

        q2.push(ewq(q1.top().v,q1.top().id)),q1.pop();

    }

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=n;i++)

        a[i]=read();

    for(int i=1;i<=m;i++)

        q1.push(qwe(a[i],i)),sm1+=a[i],si1++,bl[i]=1;

    tiao(1);

    ansl=1,ansm=q1.top().v,mn=ansm*si1-sm1+sm2-ansm*si2;//cerr<<endl;

    //cerr<<q1.top().id<<" "<<q1.top().v<<"   "<<sm1<<" "<<sm2<<"   "<<si1<<" "<<si2<<endl;

    for(int i=2;i+m-1<=n;i++)

    {

        if(bl[i-1]==1)

            sm1-=a[i-1],si1--;

        else

            sm2-=a[i-1],si2--;

        tiao(i);

        del(i);

        if(a[i+m-1]<=q1.top().v)

            q1.push(qwe(a[i+m-1],i+m-1)),sm1+=a[i+m-1],si1++,bl[i+m-1]=1;

        else

            q2.push(ewq(a[i+m-1],i+m-1)),sm2+=a[i+m-1],si2++,bl[i+m-1]=2;

        tiao(i);

        del(i);

        // cerr<<q1.top().id<<" "<<q1.top().v<<"   "<<sm1<<" "<<sm2<<"   "<<si1<<" "<<si2<<endl;

        if(q1.top().v*si1-sm1+sm2-q1.top().v*si2<mn)

            ansl=i,ansm=q1.top().v,mn=ansm*si1-sm1+sm2-ansm*si2;

    }

    printf("%lld\n",mn);

    // for(int i=1;i<=n;i++)

    // {

        // if(i>=ansl&&i<=ansl+m-1)

            // printf("%lld\n",ansm);

        // else

            // printf("%d\n",a[i]);

    // }

    return 0;

}