面对复杂的修改查询高维问题, 往往需要高级数据结构解决, 但是高级数据结构一般码量大, 容易犯错. 对于一些离线问题, 我们可以用 CDQ 分治或者整体二分通过降维等方法解决, 且因为 CDQ 分治容易理解且十分好写受到许多算法竞赛选手的欢迎.
CDQ 分治
推荐博客: http://www.cnblogs.com/mlystdcall/p/6219421.html
CDQ 分治的思想就是, 左右分治然后只计算左边修改操作对右边查询操作的影响. CDQ 分治只是提供了一种分治思想, 没有什么固定的模板, 需要具体问题具体分析, 要多多做题才能体会.
园丁的烦恼 SHOI2007 BZOJ 1935
模板题,(时间, x 坐标, y 坐标)三维偏序问题, 因为时间按照输入已经天然排好序所以不用排序.
- #include<bits/stdc++.h>
- using namespace std;
- const int N=3e6+10;
- typedef long long LL;
- int n,m,qid;
- LL ans[N];
- struct query{
- int type,x,y,aid,w; // 操作类型, x 坐标, y 坐标, 答案编号, 对答案贡献
- bool operator <(const query &rhs) const {
- return x==rhs.x ? type<rhs.type : x<rhs.x; //x 相等时要修改操作在前
- }
- }Q[N],tmp[N];
- const int L=1e7+10; LL sum[L];
- void update(int x,int v) {
- if (x) for (;x<L;x+=x&-x) sum[x]+=v;
- }
- LL query2(int x) {
- LL ret=0;
- if (x) for (;x;x-=x&-x) ret+=sum[x];
- return ret;
- }
- void Clear(int x) {
- if (x) for (;x<L && sum[x];x+=x&-x) sum[x]=0;
- }
- void CDQ(int l,int r) {
- if (l>=r) return;
- int mid=l+r>>1;
- CDQ(l,mid); CDQ(mid+1,r); // 先两边分治
- int p=l,q=mid+1,o=l-1; // 归并排序合并两边并计算左边操作对右边询问影响
- while (p<=mid && q<=r) {
- if (Q[p]<Q[q]) {
- if (Q[p].type==0) update(Q[p].y,1); // 只处理左边的修改操作
- tmp[++o]=Q[p++]; // 归并排序
- } else {
- if (Q[q].type==1) ans[Q[q].aid]+=query2(Q[q].y)*Q[q].w; // 只处理右边的查询操作
- tmp[++o]=Q[q++]; // 归并排序
- }
- }
- while (p<=mid) tmp[++o]=Q[p++];
- while (q<=r) {
- if (Q[q].type==1) ans[Q[q].aid]+=query2(Q[q].y)*Q[q].w;
- tmp[++o]=Q[q++];
- }
- for(int i=l;i<=mid;i++) if(Q[i].type==0) Clear(Q[i].y); // 清空树状数组
- for (int i=l;i<=r;i++) Q[i]=tmp[i]; // 记录归并排序后结果
- }
- int main()
- {
- cin>>n>>m;
- for (int i=1;i<=n;i++) {
- int x,y; scanf("%d%d",&x,&y); x++; y++;
- Q[++qid]=(query){0,x,y,0,0};
- }
- for (int i=1;i<=m;i++) {
- int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
- x1++; y1++; x2++; y2++;
- Q[++qid]=(query){1,x2,y2,i,1};
- Q[++qid]=(query){1,x1-1,y1-1,i,1};
- Q[++qid]=(query){1,x1-1,y2,i,-1};
- Q[++qid]=(query){1,x2,y1-1,i,-1};
- }
- CDQ(1,qid);
- for (int i=1;i<=m;i++) printf("%lld\n",ans[i]);
- return 0;
- }
- View Code
Mokia BZOJ 1176 / 简单题 BZOJ 2683
这两题似乎是一样的, 在上一题基础上修改即可.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int N=2e6+10;
- int n,s,qid,ansid;
- LL ans[N];
- struct query{
- int type,x,y,v,w,aid;
- bool operator <(const query &rhs) const {
- return x==rhs.x ? type<rhs.type : x<rhs.x;
- }
- }Q[N],tmp[N];
- const int L=2e6; LL sum[L];
- void update(int x,LL v) {
- if (x) for (;x<=n;x+=x&-x) sum[x]+=v;
- }
- LL query2(int x) {
- LL ret=0;
- if (x) for (;x;x-=x&-x) ret+=sum[x];
- return ret;
- }
- void Clear(int x) {
- if (x) for (;x<=n && sum[x];x+=x&-x) sum[x]=0;
- }
- void CDQ(int l,int r) {
- if (l>=r) return;
- int mid=l+r>>1;
- CDQ(l,mid); CDQ(mid+1,r);
- int p=l,q=mid+1,o=l-1;
- while (p<=mid && q<=r) {
- if (Q[p]<Q[q]) {
- if (Q[p].type==0) update(Q[p].y,Q[p].v);
- tmp[++o]=Q[p++];
- } else {
- if (Q[q].type==1) ans[Q[q].aid]+=Q[q].w*query2(Q[q].y);
- tmp[++o]=Q[q++];
- }
- }
- while (p<=mid) tmp[++o]=Q[p++];
- while (q<=r) {
- if (Q[q].type==1) ans[Q[q].aid]+=Q[q].w*query2(Q[q].y);
- tmp[++o]=Q[q++];
- }
- for (int i=l;i<=mid;i++) if (Q[i].type==0) Clear(Q[i].y);
- for (int i=l;i<=r;i++) Q[i]=tmp[i];
- }
- int main()
- {
- cin>>n; s=0;
- qid=0; ansid=0; int opt;
- while (scanf("%d",&opt)==1 && opt!=3) {
- int x1,y1,x2,y2,v;
- if (opt==2) {
- scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
- ans[++ansid]=(LL)s*(x2-x1+1)*(y2-x1+1);
- Q[++qid]=(query){1,x2,y2,0,1,ansid};
- Q[++qid]=(query){1,x1-1,y2,0,-1,ansid};
- Q[++qid]=(query){1,x2,y1-1,0,-1,ansid};
- Q[++qid]=(query){1,x1-1,y1-1,0,1,ansid};
- } else {
- scanf("%d%d%d",&x1,&y1,&v);
- Q[++qid]=(query){0,x1,y1,v,0,0};
- }
- }
- CDQ(1,qid);
- for (int i=1;i<=ansid;i++) printf("%lld\n",ans[i]);
- return 0;
- }
- View Code
陌上花开 BZOJ 3262
比较裸的三维偏序问题, CDQ 最擅长解决了.
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- const int N=100000+10;
- const int M=200000+10;
- struct rec{
- int x,y,z,id;
- int maxid;
- bool operator <(const rec &rhs) const {
- return x<rhs.x || x==rhs.x && y<rhs.y || x==rhs.x && y==rhs.y && z<rhs.z;
- }
- }f[N],t[N];
- int n,m;
- int c[M<<1],ans[N];
- void update(int x,int v) {
- for (;x<=m;x+=x&-x) c[x]+=v;
- }
- int query(int x) {
- int res=0;
- for (;x;x-=x&-x) res+=c[x];
- return res;
- }
- void slove(int l,int r) {
- if (l==r) return;
- int mid=(l+r)>>1;
- slove(l,mid);
- slove(mid+1,r);
- int lc=l,rc=mid+1;
- for (int i=l;i<=r;i++) {
- if (lc<=mid && f[lc].y<=f[rc].y || rc>r) t[i]=f[lc++];
- else t[i]=f[rc++];
- }
- for (int i=l;i<=r;i++) {
- if (t[i].id<=mid) update(t[i].z,1);
- else ans[t[i].id]+=query(t[i].z);
- }
- for (int i=l;i<=r;i++) {
- f[i]=t[i];
- if (f[i].id<=mid) update(f[i].z,-1);
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for (int i=1;i<=n;i++)
- scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);
- sort(f+1,f+n+1);
- for (int i=1;i<=n;i++) f[i].id=i;
- int to=0;
- for (int i=1;i<=n;i++) {
- if (i<=to) continue;
- while (f[i].x==f[to+1].x && f[i].y==f[to+1].y && f[i].z==f[to+1].z) to++;
- for (int j=i;j<=to;j++) f[j].maxid=to;
- }
- slove(1,n);
- for (int i=1;i<=n;i++) ans[f[i].id]=ans[f[i].maxid];
- sort(ans,ans+n+1);
- int now=1;
- for (int i=0;i<n;i++) {
- int sum=0;
- while (now<=n && ans[now]==i) { now++; sum++; }
- printf("%d\n",sum);
- }
- return 0;
- }
- View Code
动态逆序对 CQOI2011 BZOJ 3295
这道题很有意思也有多种解法, 非常值得多多思考!
这里讲的是 CDQ 分治的解法 (其实哪怕是 CDQ 分治也有两种解法): 看到这道题我们会比较自然想到把删除变成插入, 那么我们增加一个时间纬度, 每一个操作变成(插入时间, 位置, 值的大小) 的三维数对, 这时候每一个插入也是每一个查询, 我们以 CDQ 的方式去思考对于一个插入数对: 别的插入数对对它的影响是什么? 对于数对(tim2,pos2,val2), 它对总逆序对增加的贡献就是 tim1<tim2 && pos1<pos2 && val1>val2 的个数加上 tim1<tim2 && pos1>pos2 && val1<val2 的个数. 发现没有这是一个经典的三维偏序问题! CDQ 分治可解!
这道题还是有一些细节的, 都在代码注释里了.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int N=1e5+10;
- int n,m,qid,a[N],b[N],c[N],pos[N];
- LL ans[N];
- struct query{
- int tim,pos,val;
- bool operator <(const query &rhs) const {
- return pos<rhs.pos;
- }
- }Q[N],tmp[N];
- LL sum[N];
- void update(int x,int v) {
- for (;x<=n;x+=x&-x) sum[x]+=v;
- }
- LL query2(int x) {
- LL ret=0;
- for (;x;x-=x&-x) ret+=sum[x];
- return ret;
- }
- void CDQ(int l,int r) {
- if (l>=r) return;
- int mid=l+r>>1;
- CDQ(l,mid); CDQ(mid+1,r);
- int p=l,q=mid+1,o=l-1;
- while (p<=mid || q<=r) // 计算 tim1<tim2 && pos1<pos2 && val1>val2 的逆序对
- if (q>r || p<=mid && Q[p]<Q[q]) update(Q[p].val,1),tmp[++o]=Q[p++];
- else ans[Q[q].tim]+=query2(n)-query2(Q[q].val),tmp[++o]=Q[q++];
- for (int i=l;i<=mid;i++) update(Q[i].val,-1);
- p=mid; q=r; // 这里是一个小细节, 因为左右区间是从小到大排序, 而这里需要从大到小, 所以倒序循环
- while (p>=l || q>mid) // 计算 tim1<tim2 && pos1>pos2 && val1<val2 的逆序对
- if (q<=mid || p>=l && Q[q]<Q[p]) update(Q[p].val,1),p--;
- else ans[Q[q].tim]+=query2(Q[q].val-1),q--;
- for (int i=l;i<=mid;i++) update(Q[i].val,-1);
- for (int i=l;i<=r;i++) Q[i]=tmp[i]; // 归并结果
- }
- int main()
- {
- cin>>n>>m;
- for (int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
- for (int i=1;i<=m;i++) scanf("%d",&b[i]),c[b[i]]=1;
- for (int i=1;i<=n;i++)
- if (!c[i]) qid++,Q[qid]=(query){qid,pos[i],i};
- for (int i=m;i;i--) qid++,Q[qid]=(query){qid,pos[b[i]],b[i]};
- CDQ(1,qid);
- for (int i=1;i<=n;i++) ans[i]+=ans[i-1];
- for (int i=n;i>n-m;i--) printf("%lld\n",ans[i]);
- return 0;
- }
- View Code
[BZOJ2001] [HNOI2010]城市建设 / 洛谷 P3206
[BZOJ2141] 排队
[BZOJ3745] Norma
整体二分
https://www.cnblogs.com/Sakits/p/7990875.html
上面博客的大佬说得很好了. 整体二分就是二分答案的进阶, 就是把操作和答案区间一起二分, 通过算左边区间对答案贡献继续向左右分, 最终缩小答案区间得到答案. 这里需要特别强调的是把操作和答案一起二分, 也就是说当前答案区间 [L,R] 二分 [L,M] 和[M+1,R]时, 应该先把操作 (包括查询也修改) 分到它属于的答案区间, 在继续往下分.
整体二分和 CDQ 分治有点儿相似都是离线分治算法, 前者基于值域后者基于时间, 时间复杂度都是 logn*f(n) 这里 f(n)是分治的一层的计算时间.
POJ-2104 K-th Number
经典题, 可以用多种解法, 也可以当作整体二分模板题来练.
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int N=2e5+10;
- const int INF=0x3f3f3f3f;
- int n,m,qid,a[N],ans[N];
- struct rec{
- int type,x,y,z,aid;
- }Q[N],ql[N],qr[N];
- int sum[N];
- void update(int x,int v) {
- for (;x<=n;x+=x&-x) sum[x]+=v;
- }
- int query(int x) {
- int ret=0;
- for (;x;x-=x&-x) ret+=sum[x];
- return ret;
- }
- void solve(int L,int R,int l,int r) { // 答案值域[L,R], 操作区间[l,r]
- if (l>r) return; // 操作序列为空
- if (L==R) {
- for (int i=l;i<=r;i++)
- if (Q[i].type==1) ans[Q[i].aid]=L; // 答案唯一了
- return;
- }
- int M=L+R>>1,p=0,q=0;
- for (int i=l;i<=r;i++) {
- if (Q[i].type==0) { // 修改操作
- if (Q[i].z<=M) ql[++p]=Q[i],update(Q[i].x,1); // 注意这里树状数组插入的是位置
- else qr[++q]=Q[i];
- } else { // 查询操作
- int tmp=query(Q[i].y)-query(Q[i].x-1); // 查询位置区间 [x,y] 中值域在 [L,M] 的数的个数
- if (tmp>=Q[i].z) ql[++p]=Q[i];
- else Q[i].z-=tmp,qr[++q]=Q[i];
- }
- }
- for (int i=l;i<=r;i++)
- if (Q[i].type==0 && Q[i].z<=M) update(Q[i].x,-1); // 还原树状数组
- for (int i=1;i<=p;i++) Q[l+i-1]=ql[i]; // 把操作按答案值域分开
- for (int i=1;i<=q;i++) Q[l+p+i-1]=qr[i];
- solve(L,M,l,l+p-1); solve(M+1,R,l+p,r); // 继续分治
- }
- int main()
- {
- cin>>n>>m;
- for (int i=1;i<=n;i++) scanf("%d",&a[i]);
- for (int i=1;i<=n;i++)
- Q[++qid]=(rec){0,i,0,a[i],0};
- for (int i=1;i<=m;i++) {
- int l,r,k; scanf("%d%d%d",&l,&r,&k);
- Q[++qid]=(rec){1,l,r,k,i};
- }
- solve(-INF,INF,1,qid);
- for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
- return 0;
- }
- View Code
- BZOJ-1901: Zju2112 Dynamic Rankings
这道题是上一道题的动态版, 我的博客写了树套树的做法, 但是树套树不仅代码复杂容易写错而且常数大, 这里用试着用整体二分解决.
这题比起上一题就是多了修改操作, 那么我们把 a[x]=y 这个赋值操作拆开变成 1删除 x 位置的 a[x] 2插入 x 位置的 y . 原来的初始数组就可以变成这里的操作2 . 把操作拆分后同样整体二分树状数组做法就可以 AC 了. 有一个问题蒟蒻想了很久: 为什么这样是对的, 插入删除查询混合在一起不会错吗? 后来想通了, 因为我们按照输入顺序安排操作顺序的, 所以操作顺序是按照时间顺序的, 且因为这里是按答案值域, 所以一个赋值操作先前的 a[x]的插入和删除必定会分在同一个区间, 那么经过紧贴在一起的 + 1 和 - 1 之后, 相当于 a[x]完全没有发挥过作用所以一个 a[x]=y 的赋值操作先前的 a[x]是完全不会对答案影响的! 这个思路十分巧妙运用了基于值域二分的特性.
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int N=3e5+10;
- const int INF=0x3f3f3f3f;
- int n,m,qid,ansid,a[N],ans[N];
- struct rec{
- int type,x,y,z,aid;
- }Q[N],ql[N],qr[N];
- int sum[N];
- void update(int x,int v) {
- for (;x<=n;x+=x&-x) sum[x]+=v;
- }
- int query(int x) {
- int ret=0;
- for (;x;x-=x&-x) ret+=sum[x];
- return ret;
- }
- void solve(int L,int R,int l,int r) { // 答案值域[L,R], 操作区间[l,r]
- if (L>R || l>r) return; // 操作序列为空
- if (L==R) {
- for (int i=l;i<=r;i++)
- if (Q[i].type==1) ans[Q[i].aid]=L; // 答案唯一了
- return;
- }
- int M=L+R>>1,p=0,q=0;
- for (int i=l;i<=r;i++) {
- if (Q[i].type==0) { // 修改操作
- if (Q[i].z<=M) ql[++p]=Q[i],update(Q[i].x,Q[i].y); // 注意这里树状数组插入的是位置
- else qr[++q]=Q[i];
- } else { // 查询操作
- int tmp=query(Q[i].y)-query(Q[i].x-1); // 查询位置区间 [x,y] 中值域在 [L,M] 的数的个数
- if (tmp>=Q[i].z) ql[++p]=Q[i];
- else Q[i].z-=tmp,qr[++q]=Q[i];
- }
- }
- for (int i=l;i<=r;i++)
- if (Q[i].type==0 && Q[i].z<=M) update(Q[i].x,-Q[i].y); // 还原树状数组
- for (int i=1;i<=p;i++) Q[l+i-1]=ql[i]; // 把操作按答案值域分开
- for (int i=1;i<=q;i++) Q[l+p+i-1]=qr[i];
- solve(L,M,l,l+p-1); solve(M+1,R,l+p,r); // 继续分治
- }
- int main()
- {
- cin>>n>>m;
- for (int i=1;i<=n;i++) scanf("%d",&a[i]);
- for (int i=1;i<=n;i++)
- Q[++qid]=(rec){0,i,1,a[i],0};
- for (int i=1;i<=m;i++) {
- char c = '_';while(c != 'C' && c != 'Q') c = getchar();
- int x,y,k;
- if (c=='Q') {
- scanf("%d%d%d",&x,&y,&k);
- Q[++qid]=(rec){1,x,y,k,++ansid};
- } else {
- scanf("%d%d",&x,&y);
- Q[++qid]=(rec){0,x,-1,a[x],0};
- Q[++qid]=(rec){0,x,1,y,0};
- a[x]=y;
- }
- }
- solve(-INF,INF,1,qid);
- for (int i=1;i<=ansid;i++) printf("%d\n",ans[i]);
- return 0;
- }
- View Code
BZOJ-3110: [Zjoi2013]K 大数查询
这道题题意有点太简略了点, 注意题目 "第 a 个位置到第 b 个位置, 每个位置加入一个数 c" 的意思不是令 ab 区间的数 +=c, 而是每个位置能够容纳多个数, 令 [a,b] 区间每个位置都插入多一个数 c. 这道题可以用树套树做, 也可以用常数更小的整体二分做.
这里说整体二分的做法: 比起静态的区间第 K 小问题, 这里多了个位置插入操作, 并且是区间的位置插入, 按照我们上两题整体二分的做法, 还是二分答案值域 + 数据结构把操作分开, 但是这里需要用到区间修改和区间查询, 树状数组当然也能做到所以我选择了线段树.
这题还有一些小细节:1答案要求的是区间第 K 大, 其实也可以直接修改整体二分的代码直接变成第 K 大, 有一个懒点的做法是注意到操作一的 c 绝对值小于等于 n, 所以我们可以把 c 变成 n-c+1 做第 K 小整体二分, 输出答案的时候再还原回去即可.2注意到 n<=50000 那么 n*m=2.5*10^9> int=2.1*10^9 所以要用 longlong
- #include<bits/stdc++.h>
- using namespace std;
- const int N=1e5+10;
- typedef long long LL;
- int n,m,qid,ansid;
- LL ans[N];
- struct rec{
- LL type,x,y,z,aid;
- }Q[N],q1[N],q2[N];
- LL sum[N<<2],tag[N<<2];
- void pushup(int rt) {
- sum[rt]=sum[rt<<1]+sum[rt<<1|1];
- }
- void pushdown(int rt,LL len1,LL len2) {
- sum[rt<<1]+=tag[rt]*len1; tag[rt<<1]+=tag[rt];
- sum[rt<<1|1]+=tag[rt]*len2; tag[rt<<1|1]+=tag[rt];
- tag[rt]=0;
- }
- void update(int rt,int l,int r,int ql,int qr,LL v) {
- if (ql<=l && r<=qr) {
- sum[rt]+=v*(r-l+1); tag[rt]+=v;
- return;
- }
- int mid=l+r>>1;
- pushdown(rt,mid-l+1,r-mid);
- if (ql<=mid) update(rt<<1,l,mid,ql,qr,v);
- if (qr>mid) update(rt<<1|1,mid+1,r,ql,qr,v);
- pushup(rt);
- }
- LL query(int rt,int l,int r,int ql,int qr) {
- if (ql<=l && r<=qr) return sum[rt];
- int mid=l+r>>1; LL ret=0;
- pushdown(rt,mid-l+1,r-mid);
- if (ql<=mid) ret+=query(rt<<1,l,mid,ql,qr);
- if (qr>mid) ret+=query(rt<<1|1,mid+1,r,ql,qr);
- return ret;
- }
- void solve(LL L,LL R,int l,int r) {
- if (l>r) return;
- if (L==R) {
- for (int i=l;i<=r;i++)
- if (Q[i].type==1) ans[Q[i].aid]=L;
- return;
- }
- LL M=(L+R)/2,p=0,q=0;
- for (int i=l;i<=r;i++)
- if (Q[i].type==0) {
- if (Q[i].z<=M) q1[++p]=Q[i],update(1,1,n,Q[i].x,Q[i].y,1);
- else q2[++q]=Q[i];
- } else {
- LL tmp=query(1,1,n,Q[i].x,Q[i].y);
- if (tmp>=Q[i].z) q1[++p]=Q[i];
- else Q[i].z-=tmp,q2[++q]=Q[i];
- }
- for (int i=l;i<=r;i++)
- if (Q[i].type==0 && Q[i].z<=M) update(1,1,n,Q[i].x,Q[i].y,-1);
- for (int i=1;i<=p;i++) Q[l+i-1]=q1[i];
- for (int i=1;i<=q;i++) Q[l+p+i-1]=q2[i];
- solve(L,M,l,l+p-1); solve(M+1,R,l+p,r);
- }
- int main()
- {
- cin>>n>>m;
- for (int i=1;i<=m;i++) {
- LL opt,x,y,z; scanf("%lld%lld%lld%lld",&opt,&x,&y,&z);
- if (opt==1) Q[++qid]=(rec){0,x,y,n-z+1,0};
- else Q[++qid]=(rec){1,x,y,z,++ansid};
- }
- solve(-n,n,1,qid);
- for (int i=1;i<=ansid;i++) printf("%lld\n",n-ans[i]+1);
- return 0;
- }
- View Code
BZOJ-2738: 矩阵乘法
来源: http://www.bubuko.com/infodetail-3064162.html