做网站颜色如何搭配,建设银行泰州江洲路支行网站,seo学院培训班,做网站放广告收益首先说明#xff0c;CDQ分治与整体二分都是离线算法
CDQ分治#xff1a;
流程#xff1a;
1.我们要解决一系列问题#xff0c;这些问题一般包含修改和查询操作#xff0c;可以把这些问题排成一个序列#xff0c;用一个区间[L,R]表示。
2.分。递归处理左边区间[L,M]和…首先说明CDQ分治与整体二分都是离线算法
CDQ分治
流程
1.我们要解决一系列问题这些问题一般包含修改和查询操作可以把这些问题排成一个序列用一个区间[L,R]表示。
2.分。递归处理左边区间[L,M]和右边区间[M1,R]的问题。
3.治。合并两个子问题同时考虑到[L,M]内的修改对[M1,R]内的查询产生的影响。即用左边的子问题帮助解决右边的子问题。
经典问题三维偏序
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
typedef long long ll;
const int N100010;
const int K200010;
struct node{int x,y,z,ans,w;
}a[N],b[N];
int tot,cnt[K],k,n;
bool cmpx(node a,node b){if(a.xb.x){if(a.yb.y) return a.zb.z;return a.yb.y;}return a.xb.x;
}
bool cmpy(node a,node b){if(a.yb.y) return a.zb.z;return a.yb.y;
}
int c[K];
int lowbit(int x){return x(-x);}
void add(int i,int x){for(;ik;ilowbit(i))c[i]x;
}
int sum(int i){int res0;for(;i0;i-lowbit(i))resc[i];return res;
}
void cdq(int l,int r){if(lr) return;int mid(lr)1;cdq(l,mid);cdq(mid1,r);sort(al,amid1,cmpy);sort(amid1,ar1,cmpy);int imid1,jl;for(;ir;i){while(a[j].ya[i].yjmid){add(a[j].z,a[j].w);j;}a[i].anssum(a[i].z);}for(il;ij;i)add(a[i].z,-a[i].w);
}
int main(){scanf(%d%d,n,k);for(int i1;in;i){scanf(%d%d%d,b[i].x,b[i].y,b[i].z);}sort(b1,bn1,cmpx);int c0;for(int i1;in;i){c;if(b[i].x!b[i1].x||b[i].y!b[i1].y||b[i].z!b[i1].z){a[tot]b[i];a[tot].wc;c0;}}cdq(1,tot);for(int i1;itot;i)cnt[a[i].ansa[i].w-1]a[i].w;for(int i0;in;i) printf(%d\n,cnt[i]);return 0;
} 四维偏序
整体二分
产生原因
对于单个查询而言我们可以采用预处理二分答案的方法解决
但往往我们要回答的是一系列的查询所以我们将所有操作包括修改和查询一起二分进行分治即整体二分。
模板Meteors
#includeiostream
#includecstdio
using namespace std;
#define ll long long
#define N 300010
inline int read() {char cgetchar(); int x 0, f 1;while(c0||c9){if(c-) f-1; cgetchar();}while(c0c9) xx*10c-0, cgetchar();return x*f;
}
struct Node{int head,id;ll need;
}node[N],node_[N1];
int n,m,k,L[N],R[N];
ll A[N];
int ans[N],nxt[N],to[N],idx;
ll tmp[N1];
void add_edge(int a,int b){nxt[idx]node[a].head;to[idx]b;node[a].headidx;
}
void add(int x,ll y){while(x2*m){tmp[x]y;xx-x;}
}
ll sum(int x){ll sum0;while(x){sumtmp[x];x-x-x; } return sum;
}
void solve(int l,int r,int x,int y){if(xy) return;if(lr){for(int ix;iy;i) ans[node[i].id]l;return;}int mid(lr)1,tl0,trn;for(int il;imid;i){add(L[i],A[i]);add(R[i]1,-A[i]);}for(int ix;iy;i){ll tmp10;for(int jnode[i].head;jtmp1node[i].need;jnxt[j])tmp1sum(to[j]m)sum(to[j]);if(tmp1node[i].need) node_[tl]node[i];else node_[tr]node[i],node_[tr].need-tmp1;}for(int il;imid;i){add(L[i],-A[i]),add(R[i]1,A[i]);} for(int i1;itl;i) node[xi-1]node_[i];for(int in1;itr;i) node[xtli-n-1]node_[i];solve(l,mid,x,xtl-1);solve(mid1,r,y-trn1,y);
}
int main(){scanf(%d%d,n,m);for(int i1,a;im;i){aread();add_edge(a,i);} for(int i1;in;i){node[i].needread();node[i].idi;} scanf(%d,k);for(int i1;ik;i){scanf(%d%d%lld,L[i],R[i],A[i]);} for(int i1;ik;i)if(R[i]L[i]) R[i]m; solve(1,k1,1,n);for(int i1;in;i)ans[i]k1?printf(NIE\n):printf(%d\n,ans[i]);
}异同
同
1.都是按时间进行分治
2.代码很像不完全一样这在异中会讲到
3.复杂度都是O(f(n)logn)
异
1.整体二分有二分答案操作
2.适用范围不同
