[bzoj1112][POI2008]砖块KLO

哇超级兴奋！自己调了一道treap...

调了一上午板子，又调了一下午这道题。POI的题面和bzoj不一样，然后bzoj又炸了，，真让人头大呢。

终于在看了一个小时题面之后（好叭闲来着），，，bzoj好了，看了一下中文题面。

mad我为啥不上博客直接找题面。。

以上P话下面题面。

Description

N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.

Input

第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000

Output

最小的动作次数

Sample Input

5 3

3
9
2
3
1

Sample Output

HINT

原题还要求输出结束状态时,每柱砖的高度.本题略去.

显然对于一个固定的区间把所有数都变成中位数那么大是花费最少的。如果区间长度是偶数，中位数取两个之中哪个都行。

然后我们要做的就是求每个区间第k/2大的数，以及区间内大于它的数的和，小于它的数的和。枚举是O(n)的。

我们要维护区间长度固定是k，所以枚举到下一个区间插入一个元素a[i]，弹出元素a[i-k]。

无脑treap水过。但是我不会求前驱的和啊于是调了一下午555...

话说blackjack的代码是找hzwer学长改的叭...被我发现了...但还是很强！

#include<bits/stdc++.h>
#define L T[x].ls
#define R T[x].rs
using namespace std;
typedef long long ll;
const int N=100010;
int root,sz;
ll tot;
struct Node{
    ll val,sz,cnt;int ls,rs,key;ll sum;
}T[N];
void ref(int x){
    T[x].sz=T[L].sz+T[R].sz+T[x].cnt;
    T[x].sum=T[L].sum+T[R].sum+T[x].cnt*T[x].val;
}
void zig(int &x){
    int y=R;
    T[x].rs=T[y].ls;T[y].ls=x;
    T[y].sz=T[x].sz;ref(x);ref(y);x=y;
}
void zag(int &x){
    int y=L;
    T[x].ls=T[y].rs;T[y].rs=x;
    T[y].sz=T[x].sz;ref(x);ref(y);x=y;
}
void ins(int &x,ll v){
    if(!x){
        x=++sz;
        T[x]=(Node){v,1,1,0,0,rand(),v};
        return;
    }
    T[x].sz++;T[x].sum+=v;
    if(T[x].val==v){
        T[x].cnt++;
        return;
    }
    if(T[x].val<v){
        ins(R,v);
        if(T[R].key<T[x].key)
        zig(x);
    }
    else{
        ins(L,v);
        if(T[L].key<T[x].key)
        zag(x);
    }
}
void del(int &x,int v){
    if(!x)return;
    if(T[x].val==v){
        if(T[x].cnt>1){
            T[x].cnt--;T[x].sz--;T[x].sum-=v;
            return;
        }
        if(!(L*R)){
            x=L+R;return;
        }
        if(T[L].key<T[R].key)
            zag(x),del(x,v);
        else
            zig(x),del(x,v);
    }
    else{
        T[x].sz--;T[x].sum-=v;
        if(T[x].val<v)del(R,v);
        else del(L,v);
    }
}
int qnum(int x,int rk){
    if(!x)return 0;
    if(rk<=T[L].sz)
    return qnum(L,rk);
    if(rk>T[L].sz+T[x].cnt){
        tot+=T[L].sum+T[x].val*T[x].cnt;
        return qnum(R,rk-T[L].sz-T[x].cnt);
    }
    rk-=T[L].sz;
    tot+=T[x].val*(rk-1);
    tot+=T[L].sum;
    return T[x].val;
}
int a[N];
int main(){
    int n,k;scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    ll ans=1e15,sum=0;
    int p=(k+1>>1)-1,f,m;
    for(int i=0;i<k;i++)
    ins(root,a[i]),sum+=a[i];
    for(int i=k;i<=n;i++){
        tot=0;ins(root,a[i]);
        del(root,a[i-k]);sum+=a[i]-a[i-k];
        int t=qnum(root,k+1>>1);
        ll cost=t*p-tot;
        cost+=(sum-tot)-t*(k-p);
        if(ans>cost){
            ans=cost;f=i;m=t;
        }
    }
    cout<<ans<<endl;
    //POI上要用下面这些       
    //for(int i=f-k+1;i<=f;i++)
    //a[i]=m;
    //for(int i=1;i<=n;i++)
    //printf("%d\n",a[i]);
}

%%%！

[bzoj1112][POI2008]砖块KLO

推荐阅读