CDQ 分治 P3810 【模板】三维偏序 / 陌上花开 模板，没啥好说的 代码： #include using namespace std; #define int long long const int N=1e5+5; const int K=2e5+5; int n,k,m,t; int res[N]; struct Element { int a,b,c,cnt,res; bool operator!=(Element other) const { return a!=other.a||b!=other.b||c!=other.c; } }e[N],ue[N]; struct BIT { int node[K]; int lowbit(int x) {return x&-x;} void add(int pos,int val) { while(pos>1; cdq(l,mid); cdq(mid+1,r); sort(ue+l,ue+mid+1,cmpB); sort(ue+mid+1,ue+r+1,cmpB); int i=l,j=mid+1; while(j>n>>k; for(int i=1;i>e[i].a>>e[i].b>>e[i].c; sort(e+1,e+n+1,cmpA); for(int i=1;i `#include using namespace std; #define int long long const int N=1e5+5; const int K=2e5+5; int n,k,m,t; int res[N]; struct Element { int a,b,c,cnt,res; bool operator!=(Element other) const { return a!=other.a||b!=other.b||c!=other.c; } }e[N],ue[N]; struct BIT { int node[K]; int lowbit(int x) {return x&-x;} void add(int pos,int val) { while(posnode[pos]+=val,pos+=lowbit(pos); } int ask(int pos) { int res=0; while(pos) res+=node[pos],pos-=lowbit(pos); return res; } }bit; bool cmpA(Element x,Element y) { if(x.a!=y.a) return x.ay.a; if(x.b!=y.b) return x.by.b; return x.cy.c; } bool cmpB(Element x,Element y) { if(x.b!=y.b) return x.by.b; return x.cy.c; } void cdq(int l,int r) { if(l==r) return; int mid=(l+r)>>1; cdq(l,mid); cdq(mid+1,r); sort(ue+l,ue+mid+1,cmpB); sort(ue+mid+1,ue+r+1,cmpB); int i=l,j=mid+1; while(j while(iue[i].bue[j].b) bit.add(ue[i].c,ue[i].cnt),i++; ue[j].res+=bit.ask(ue[j].c),j++; } for(int k=l;kbit.add(ue[k].c,-ue[k].cnt); } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>k; for(int i=1;i>e[i].a>>e[i].b>>e[i].c; sort(e+1,e+n+1,cmpA); for(int i=1;i t++; if(e[i]!=e[i+1]) { ue[++m]={e[i].a,e[i].b,e[i].c,t,0}; t=0; } } cdq(1,m); for(int i=1;ires[ue[i].res+ue[i].cnt-1]+=ue[i].cnt; for(int i=0;ires[i]'\n'; return 0; }` P2163 [SHOI2007] 园丁的烦恼 甚至不需要使用 CDQ 分治，二位数点问题，算是下一题的弱化版本，直接一个树状数组就够了。 代码： #include using namespace std; const int N=5e5+5, M=3e6+5; int n,m,cnt; struct nd{ int x,y,k,id; }q[N*5]; int ans[N]; vector v; struct BIT{ int tr[M]; int lowbit(int x) {return x&-x;} void add(int p,int v){ while(p>n>>m; for(int i=1;i>x>>y; q[++cnt]={x,y,0,0}; v.push_back(y); } for(int i=1;i>a>>b>>c>>d; q[++cnt]={c,d,1,i}; q[++cnt]={a-1,d,-1,i}; q[++cnt]={c,b-1,-1,i}; q[++cnt]={a-1,b-1,1,i}; v.push_back(b-1); v.push_back(d); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i `#include using namespace std; const int N=5e5+5, M=3e6+5; int n,m,cnt; struct nd{ int x,y,k,id; }q[N*5]; int ans[N]; vectorint> v; struct BIT{ int tr[M]; int lowbit(int x) {return x&-x;} void add(int p,int v){ while(ptr[p]+=v,p+=lowbit(p); } int ask(int p){ int res=0; while(p) res+=tr[p],p-=lowbit(p); return res; } }bit; bool cmp(nd a,nd b){ if(a.x!=b.x) return a.xb.x; return a.k==0; } int id(int y){ return lower_bound(v.begin(),v.end(),y)-v.begin()+1; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1;i int x,y; cin>>x>>y; q[++cnt]={x,y,0,0}; v.push_back(y); } for(int i=1;i int a,b,c,d; cin>>a>>b>>c>>d; q[++cnt]={c,d,1,i}; q[++cnt]={a-1,d,-1,i}; q[++cnt]={c,b-1,-1,i}; q[++cnt]={a-1,b-1,1,i}; v.push_back(b-1); v.push_back(d); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;iq[i].y=id(q[i].y); sort(q+1,q+1+cnt,cmp); for(int i=1;i if(q[i].k==0) bit.add(q[i].y,1); else ans[q[i].id]+=q[i].k*bit.ask(q[i].y); } for(int i=1;ians[i]"\n"; return 0; }` P4390 [BalkanOI 2007] Mokia 摩基亚 上一题的升级版，在树状数组+二位前缀和的基础上增加了一个时间维度，想到使用 CDQ 分治来处理，在上一题的基础上稍加修改即可，思路上没有区别。 代码： #include using namespace std; const int N=2e5+5; const int M=2e6+5; int w,op,tot,qcnt; int ans[N]; struct Node{ int time,type,x,y,val,id; bool operator>1; cdq(l,mid); cdq(mid+1,r); sort(q+l,q+mid+1,cmpX); sort(q+mid+1,q+r+1,cmpX); int i=l,j=mid+1; while(j>op>>w; w++; int time=0; while(cin>>op&&op!=3){ time++; if(op==1){ int x,y,val; cin>>x>>y>>val; x++; y++; q[++tot]={time,1,x,y,val,0}; } else{ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; x1++; y1++; x2++; y2++; qcnt++; q[++tot]={time,2,x2,y2,1,qcnt}; q[++tot]={time,2,x1-1,y2,-1,qcnt}; q[++tot]={time,2,x2,y1-1,-1,qcnt}; q[++tot]={time,2,x1-1,y1-1,1,qcnt}; } } sort(q+1,q+tot+1); cdq(1,tot); for(int i=1;i `#include using namespace std; const int N=2e5+5; const int M=2e6+5; int w,op,tot,qcnt; int ans[N]; struct Node{ int time,type,x,y,val,id; bool operator(const Node &t) const{ if(time!=t.time) return timet.time; if(x!=t.x) return xt.x; if(y!=t.y) return yt.y; return typet.type; } }q[N],tmp[N]; struct BIT{ int node[M]; int lowbit(int x) {return x&-x;} void add(int pos,int val){ while(posnode[pos]+=val,pos+=lowbit(pos); } int ask(int pos) { int res=0; while(pos) res+=node[pos],pos-=lowbit(pos); return res; } void clear(int pos){ while(pos if(!node[pos]) break; node[pos]=0; pos+=lowbit(pos); } } }bit; bool cmpX(const Node &a,const Node &b){ if(a.x!=b.x) return a.xb.x; if(a.y!=b.y) return a.yb.y; return a.typeb.type; } void cdq(int l,int r){ if(l==r) return; int mid=(l+r)>>1; cdq(l,mid); cdq(mid+1,r); sort(q+l,q+mid+1,cmpX); sort(q+mid+1,q+r+1,cmpX); int i=l,j=mid+1; while(j while(iq[i].xq[j].x){ if(q[i].type==1) bit.add(q[i].y,q[i].val); i++; } if(q[j].type==2) ans[q[j].id]+=q[j].val*bit.ask(q[j].y); j++; } for(int k=l;k if(q[k].type==1) bit.clear(q[k].y); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>op>>w; w++; int time=0; while(cin>>op&&op!=3){ time++; if(op==1){ int x,y,val; cin>>x>>y>>val; x++; y++; q[++tot]={time,1,x,y,val,0}; } else{ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; x1++; y1++; x2++; y2++; qcnt++; q[++tot]={time,2,x2,y2,1,qcnt}; q[++tot]={time,2,x1-1,y2,-1,qcnt}; q[++tot]={time,2,x2,y1-1,-1,qcnt}; q[++tot]={time,2,x1-1,y1-1,1,qcnt}; } } sort(q+1,q+tot+1); cdq(1,tot); for(int i=1;ians[i]'\n'; return 0; }`
CDQ 分治
笔记