[ZJOI 2013] bzoj3110 K大数查询 (整体二分)
昨天晚上写了一道最裸的cdq分治的题陌上花开,自己做出来的,感觉又有了一定的领悟。感觉其实cdq分治就相当于主席树的用处,主席树又叫函数式线段树,顾名思义可以拿来当一个函数用,相当于建出来之后就一劳永逸了,来一个询问解决一个。但是有些题目并不要求在线,所以并不需要把一整个主席树都建出来,而是每次都在线地去找它的前缀,然后cdq分治保证了每个点都有不超过logn个前缀,并且在计算i的时候它的前缀已经全部处理完了。 所以说cdq分治是很节约空间的。可以把O(nlogn)的空间强力降到O(n)。网上很多人说cdq的内存是nlogn的,我真的很奇怪,整个程序都没有动态开内存,全局数组开了多少自己还不知道吗。。 比如说陌上花开一题,每个花有三个属性,对每个花求有多少花三个属性都不超过它。常规解法是排序之后树状数组套treap或者主席树,然后扫描。cdq分治的话分治套树状数组就可以了,先按a排序,每一次分治用划分的思想将b划分开,然后c用树状数组来求前缀和。 这道题稍微难一点。我开始的时候想了一下数据结构解法,应该是外面一个线段树里面一个主席树。线段树的话涉及区间修改需要打标记,比较麻烦,可以用支持区间修改区间查询的树状数组来代替。由于时间不是很充足,只是自己YY了一下,不知道能不能实现。 分治的做法比较给力。首先其实这个应该叫整体二分,并不是传统的cdq分治。一般的cdq分治不断划分就行了,但是这个整体二分在划分的基础上还有个二分答案。把修改和询问先按时间顺序排好(其实就是输入顺序),划分的时候按照修改可能给出的影响以及询问可能的答案区间来分。由于并不一定对半分,l2不能直接设为mid+1,需要开两个栈来保持,也可以像我这样l1正着走,l2倒着走,然后再reverse。
#include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 50010; #define rep(i,a,b) for(int i=a;i<=b;++i) int N,M; namespace BIT { int c1[MAXN],c2[MAXN]; inline void add(int*c,int i,int b) { for (; i<=N; i+=i&-i) c[i] += b; } inline int sum(int*c,int i) { int r = 0; for (; i>0; i-=i&-i) r += c[i]; return r; } inline void add(int l,int r,int c) { add(c1,l,c),add(c1,r+1,-c); add(c2,-c*(l-1)),add(c2,c*r); } inline int pre(int i) { if (!i) return 0; return sum(c1,i)*i + sum(c2,i); } inline int sum(int l,int r) { return pre(r) - pre(l-1); } }; struct dot { int l,r,c,tp,id; void get(int _id) { id = _id; scanf("%d%d%d%d",&tp,&l,&r,&c); } } po[MAXN],np[MAXN]; int ans[MAXN]; void cdq(int L,int R,int l,int r) { using namespace BIT; if (L > R) return; if (l == r) { rep(i,L,R) if (po[i].tp == 2) ans[po[i].id] = l; return; } int mid = (l + r) >> 1; int l1 = L,l2 = R; rep(i,R) { if (po[i].tp == 1) { if (po[i].c <= mid) np[l1++] = po[i]; else { np[l2--] = po[i]; add(po[i].l,po[i].r,1); } } else { int cnt = sum(po[i].l,po[i].r); if (cnt < po[i].c) { po[i].c -= cnt; np[l1++] = po[i]; } else np[l2--] = po[i]; } } reverse(np+l2+1,np+R+1); rep(i,R) { po[i] = np[i]; if (po[i].tp==1 && po[i].c>mid) add(po[i].l,-1); } cdq(L,l1-1,mid); cdq(l1,R,mid+1,r); } bool has[MAXN]; int main() { scanf("%d%d",&N,&M); rep(i,1,M) po[i].get(i),po[i].tp==2&&(has[i]=1); cdq(1,M,N); rep(i,M) if (has[i]==1) printf("%dn",ans[i]); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |