BZOJ 1112 [POI2008]砖块Klo

题目大意

给你一个有N个元素的序列，每个元素+1/-1需要付出1的代价，求将连续K个元素变成相同所需要的最小代价。

这道题首先是贪心部分。假设N==K，那么如何规划才可以使得代价最小呢?很简单，我们先将其排序，之后先钦定一个，考虑更改对结果带来的影响。如果+1的话，比它大的所有元素更改代价-1，比它小的所有元素更改代价+1，因此易知如果放在中位数位置的话比它小的和比它大的元素个数一样，无论加大还是减小目标都会使得代价变高。之后就可以开始考虑其他事情了。

也就是说我们要枚举所有可能的区间，找到中位数求出代价。如何操作？

使用权值线段树维护效果还可以，主要是没写过这次就尝试写了一发，似乎比Splay好写那么一点23333

#include <cstdio>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
int n,k,h[100010],cnt[5000010],want[2],num;
long long sum[5000010],pre[100010],ans=0x7f7f7f7f7f7f7f7fll,lsum,rsum;
void addnum(int pos,int l,int r,int tx)
{
    if(l==r) {cnt[pos]++;sum[pos]=cnt[pos]*l;return;}
    int mid=(l+r)>>1;
    if(tx<=mid) addnum(lson,l,mid,tx);
    else addnum(rson,mid+1,r,tx);
    cnt[pos]=cnt[lson]+cnt[rson];
    sum[pos]=sum[lson]+sum[rson];
}
void delnum(int pos,int l,int r,int tx)
{
    if(l==r) {cnt[pos]--;sum[pos]=cnt[pos]*l;return;}
    int mid=(l+r)>>1;
    if(tx<=mid) delnum(lson,l,mid,tx);
    else delnum(rson,mid+1,r,tx);
    cnt[pos]=cnt[lson]+cnt[rson];
    sum[pos]=sum[lson]+sum[rson];
}
long long getsum(int pos,int l,int r,int tx)
{
    if(cnt[pos]==tx) return sum[pos];
    if(l==r) return min(cnt[pos],tx)*l;
    long long tmp=0;
    int mid=(l+r)>>1;
    tmp+=getsum(lson,l,mid,min(cnt[lson],tx));
    if(cnt[lson]<tx) tmp+=getsum(rson,mid+1,r,tx-cnt[lson]);
    return tmp;
}
int getnum(int pos,int l,int r,int tx)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(tx<=cnt[lson]) return getnum(lson,l,mid,tx);
    else return getnum(rson,mid+1,r,tx-cnt[lson]);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%d",h+i);
    for(int i=1;i<=n;++i) pre[i]=pre[i-1]+h[i];//Long long
    for(int i=0;i<k;++i) addnum(1,0,1000000,h[i]);
    if(k%2) want[0]=want[1]=(k>>1)+1;
    else want[0]=k>>1,want[1]=want[0]+1;
    for(int i=k;i<=n;++i)
    {
        delnum(1,0,1000000,h[i-k]);
        addnum(1,0,1000000,h[i]);
        for(int j=0;j<2;++j)
        {
            if(j==1&&want[j]==want[j-1]) break;
            lsum=getsum(1,0,1000000,want[j]-1);
            num=getnum(1,0,1000000,want[j]);
            rsum=pre[i]-pre[i-k]-lsum-num;
            ans=min(ans,1ll*(want[j]-1)*num-lsum+rsum-1ll*num*(k-want[j]));
        }
    }
    printf("%lld\n",ans);
    return 0;
}