NEERC 17 G The Great Wall (treap)

题意：

        给你一个数列，每个点有abc三个值，现在让你画两个区间x，y，区间大小为r，区间不可以完全重合，当一个点没有被区间覆盖时值为a,被一个区间覆盖时值为b，两个区间为c，问第k小的数列数值总和为多少

思路：

       我们二分答案val，寻找小于val的有多少对x，y
       首先思考当x,y没有重合的时候，我们枚举后面的区间y的起点i，设区间权值和为v，我们每次询问小于val-v的有多少个，询问完后将,[i-r+1,i]这个区间的值加入到一个数据结构里面，支持插入和查询排名，treap就能满足
       然后我们思考当两个区间有重合的时候，区间可化为$g_i+f_i$,其中
                            $g_i=\sum_{0}^{i-1}(c_i-2*b_i)+\sum_{i}^{i+r-1}(c_i-b_i)$

                            $f_i=\sum_{0}^{i-1}(2*b_i-c_i)+\sum_{i}^{i+r-1}(b_i)$
       这个式子是什么意思呢，可以画一下图，就发现这两个式子和会使得区间相互抵消，最后就是我们希望的结果，那么我们和之前一样，不停查询，插入即可，但是这里记得及时删除无法和后面区间产生重合的区间，支持插入，查询排名和删除，treap依旧能满足
       在开始之前将$b_i-a_i$，$c_i-a_i$，写的时候会更加清晰，在输出答案之前加上$\sum_{1}^{n}a_i$就行
       发现好多大佬都是用树状数组线段树写的，不是很懂是什么原理，我这样的渣渣只能用treap莽了QAQ

错误及反思：

        NEERC虽然有的题目很麻烦，但是意外的数据都没坑，有点爽

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 31000;int n,k,r;
int a[N],b[N],c[N];
long long preb[N],pre2bc[N],precb[N];
struct Treap{int l,r,dat;long long val;int cnt,size;
}t[N];
int tot,root;
long long INF = 1000000000000000;int New(long long val){t[++tot].val=val;t[tot].dat=rand();t[tot].l=t[tot].r=0;t[tot].cnt = t[tot].size =1;return tot;
}void Update(int p){ t[p].size=t[t[p].l].size+t[t[p].r].size+t[p].cnt; }
void Build(){ New(-INF); New(INF); root=1,t[1].r=2; Update(root); }
void zig(int &p){ int q=t[p].l; t[p].l=t[q].r,t[q].r=p,p=q; Update(t[p].r),Update(p);}
void zag(int &p){ int q=t[p].r; t[p].r=t[q].l,t[q].l=p,p=q; Update(t[p].l),Update(p); }int GetRankByVal(int p,long long val){if(p==0) return 0;if(val==t[p].val) return t[t[p].l].size+t[p].cnt;if(val<t[p].val) return GetRankByVal(t[p].l,val);return GetRankByVal(t[p].r,val)+t[t[p].l].size+t[p].cnt;
}void Insert(int &p,long long val){if(p==0){p=New(val);return ;}if(val==t[p].val){t[p].cnt++,Update(p);return ;}if(val<t[p].val){Insert(t[p].l,val);if(t[p].dat<t[t[p].l].dat) zig(p);}else{Insert(t[p].r,val);if(t[p].dat<t[t[p].r].dat) zag(p);}Update(p);
}void Remove(int &p,long long val){if(p==0) return ;if(val==t[p].val){if(t[p].cnt>1){t[p].cnt--,Update(p);return ;}if(t[p].l||t[p].r){if(t[p].r==0||t[t[p].l].dat>t[t[p].r].dat)zig(p),Remove(t[p].r,val);else zag(p),Remove(t[p].l,val);Update(p);}else p=0;return ;}val<t[p].val?Remove(t[p].l,val):Remove(t[p].r,val);Update(p);
}int cal1(long long x){tot=0; Build();int ans=0;for(int i=r;i+r-1<=n;i++){ans+=GetRankByVal(root,x-preb[i+r-1]+preb[i-1])-1;Insert(root,preb[i]-preb[i-r]);}return ans;
}int cal2(long long x){tot=0; Build();int ans=0;for(int i=1;i+r-1<=n;i++){ans+=GetRankByVal(root,x-(pre2bc[i-1]+preb[i+r-1]-preb[i-1]))-1;Insert(root,-pre2bc[i-1]+precb[i+r-1]-precb[i-1]);if(i>=r) Remove(root,-pre2bc[i-r]+precb[i]-precb[i-r]);}return ans;
}int judge(long long x){int ans=0;ans+=cal1(x);ans+=cal2(x);return ans;
}int main(){scanf("%d%d%d",&n,&r,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i]-=a[i];for(int i=1;i<=n;i++) scanf("%d",&c[i]),c[i]-=a[i];for(int i=1;i<=n;i++) preb[i]=1ll*preb[i-1]+1ll*b[i];for(int i=1;i<=n;i++) pre2bc[i]=1ll*pre2bc[i-1]+2ll*b[i]-1ll*c[i];for(int i=1;i<=n;i++) precb[i]=1ll*precb[i-1]+1ll*c[i]-1ll*b[i];long long l=0,r=3e10;while(l+1<r){long long m=(l+r)/2;if(judge(m)>=k) r=m;else l=m;}for(int i=1;i<=n;i++) r+=1ll*a[i];printf("%lld\n",r);}