BZOJ 1112 [POI2008]砖块Klo（可持久化线段树）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
typedef long long LL;
int n,m,i,x,y,z,ans;
int l[N*40],r[N*40],v[N*40],tot,root[N],num[N];
LL s[N*40];
int cmp(int i,int j){return num[i]<num[j];}
int rk[N],sa[N];  //sa:该数字对应原数列的下标 
int build(int a,int b){
    int x=++tot; v[x]=s[x]=0;
    if(a==b)return x;
    int mid=(a+b)>>1;
    return l[x]=build(a,mid),r[x]=build(mid+1,b),x;
}
// x版本c位置+p,在s中记录+num[sa[c]],统计权值线段树上真值的区间和。
int change(int x,int a,int b,int c,int p){
    int y=++tot;v[y]=v[x]+p;s[y]=s[x]+num[sa[c]];
    if(a==b)return y;
    int mid=(a+b)>>1;
    if(c<=mid)l[y]=change(l[x],a,mid,c,p),r[y]=r[x];
    else l[y]=l[x],r[y]=change(r[x],mid+1,b,c,p);
    return y;
}
int kth(int x,int y,int a,int b,int k){
    if(a==b)return a;
    int mid=(a+b)>>1;
    if(v[l[y]]-v[l[x]]>=k)return kth(l[x],l[y],a,mid,k);
    else return kth(r[x],r[y],mid+1,b,k-v[l[y]]+v[l[x]]);
}
LL abs(LL x){return x<0?-x:x;}
LL query(int x,int y,int a,int b,int c){
    if(a==b)return 1LL*abs(num[sa[a]]-num[sa[c]])*(v[y]-v[x]);
    int mid=(a+b)>>1;
    if(c<=mid){
        return query(l[x],l[y],a,mid,c)+s[r[y]]-s[r[x]]-1LL*num[sa[c]]*(v[r[y]]-v[r[x]]);
    }else{
        return query(r[x],r[y],mid+1,b,c)+1LL*num[sa[c]]*(v[l[y]]-v[l[x]])-(s[l[y]]-s[l[x]]);
    }
} 
int main(){
    while(~scanf("%d%d",&n,&m)){
        root[0]=0;tot=0; 
        for(int i=1;i<=n;i++)scanf("%d",num+i);  
        for(int i=1;i<=n;i++)sa[i]=i;  
        sort(sa+1,sa+n+1,cmp); 
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        build(1,n);
        for(int i=1;i<=n;i++)root[i]=change(root[i-1],1,n,rk[i],1);
        LL ans=0x3f3f3f3f3f3f3f3f;
        for(int i=1;i<=n-m+1;i++){
            int id=kth(root[i-1],root[i+m-1],1,n,(m+1)>>1);
            ans=min(ans,query(root[i-1],root[i+m-1],1,n,id));
        }printf("%lld\n",ans);
    }return 0;
}