【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1112
【题目大意】
给出一个数列，对于一个操作，你可以对一个数+1，或者一个数-1，
问若使得数列中出现长度为m的连续相同的数，最少需要的操作数。
【题解】
我们发现对于固定区间求最小操作，等价于求区间中数距离中位数差值和最小，
我们发现区间中位数可以利用主席树求区间kth来实现，
同时在主席树上维护权值线段树的区间真值和，那么对于每个区间中的数，
就能分别维护比中位数小的部分的和以及比中位数大的部分的和，
分别与中位数的倍数做加减运算即可。
我们枚举区间的位置，保留最小值，复杂度O(nlogn)。
【代码】
#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
",ans);
}return 0;
}