【BZOJ1112】砖块Klo

本文主要是介绍【BZOJ1112】砖块Klo，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门
题解：
显然每次取中位数，暴力枚举区间，用一个平衡树维护就好啦

ps: splay插入时忘记旋转，T得飞起

//by sdfzchy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define pa t[x].fa
#define ls t[x].ch[0]
#define rs t[x].ch[1]
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010,mod=1e9+7;
int n,m,a[N],k;
inline int in()
{char tmp=getchar();int res=0,f=1;while((tmp<'0'||tmp>'9')&&tmp!='-')tmp=getchar();if(tmp=='-') f=-1,tmp=getchar();while(tmp>='0'&&tmp<='9') res=(res<<1)+(res<<3)+(tmp^48),tmp=getchar();return res*f;
}
int root;
LL ans=inf;
struct node
{int ch[2],siz,fa,cnt;LL val,sum;
}t[N];
inline int gi(int x) {return t[pa].ch[1]==x;}
inline void upd(int x)
{t[x].siz=t[ls].siz+t[rs].siz+t[x].cnt;t[x].sum=t[ls].sum+t[rs].sum+t[x].cnt*t[x].val;
}
void rot(int x)
{int f=pa,g=t[pa].fa,o=gi(x);if(g) t[g].ch[gi(f)]=x;t[x].fa=g;t[f].ch[o]=t[x].ch[!o];t[t[x].ch[!o]].fa=f;t[x].ch[!o]=f;t[f].fa=x;upd(f),upd(x);
}void splay(int x,int tar)
{for(;pa!=tar;rot(x))if(t[pa].fa!=tar)rot((gi(x)==gi(pa))?pa:x);if(!tar) root=x;
}
int cnt;
void newnode(int &x,int val)
{x=++cnt;t[x].ch[0]=t[x].ch[1]=0;t[x].siz=t[x].cnt=1;t[x].val=t[x].sum=val;
}
void ins(int &x,int val,int fa)
{if(!x) {newnode(x,val);pa=fa;splay(x,0);return;}t[x].siz++;if(t[x].val==val) {t[x].cnt++;t[x].sum+=val;return;}if(val>t[x].val) ins(rs,val,x);else ins(ls,val,x);upd(x);
}
int find(int val)
{int x=root;while(x){if(t[x].val==val) break;if(val>t[x].val)  x=rs;else x=ls;}if(x) splay(x,0);return x;
}
void del(int val)
{int x=find(val);if(t[x].cnt>1) {t[x].cnt--;t[x].siz--;t[x].sum-=val;return;}if(!ls&&!rs) root=0;if(!ls) {root=rs;t[rs].fa=0;return;}if(!rs) {root=ls;t[ls].fa=0;return;}int pos=t[x].ch[0];while(t[pos].ch[1]) pos=t[pos].ch[1];splay(pos,x);t[pos].ch[1]=rs;t[rs].fa=pos;t[pos].fa=0;root=pos;upd(pos);
}int kth(int kk)
{int x=root;while(x){if(t[ls].siz>=kk) x=ls;else if(t[ls].siz+t[x].cnt<kk) kk-=t[ls].siz+t[x].cnt,x=rs;else return x;}
}void ga()
{int x=kth((k+1)>>1);splay(x,0);ans=min(ans,abs(t[x].val*t[ls].siz-t[ls].sum)+abs(t[x].val*t[rs].siz-t[rs].sum));
}int main()
{ans=10000000000000000ll;n=in(),k=in();for(int i=1;i<=n;i++) a[i]=in();for(int i=1;i<=k;i++) ins(root,a[i],0);ga();for(int i=k+1;i<=n;i++){del(a[i-k]);ins(root,a[i],0);ga();}printf("%lld",ans);return 0;
}

这篇关于【BZOJ1112】砖块Klo的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---