多方查找找到了2008年陈丹琪引入CDQ分治的 从《Cash》谈一类分治算法的应用.doc ,CDQ分治的名字由来也是她.
什么叫CDQ分治呢?来看一道二维数点题p1357.
看了一眼题,我会树状数组!
现在拿它来引入CDQ分治.先全部按照x排序,由于区间[mid+1,r]不会再对区间[l,mid]有贡献,对于区间[l,r]内的贡献都可以分三步进行.
1.算区间[l,mid]内部相互的贡献
2.算区间[mid+1,r]内部相互的贡献
3.算[l,mid]对于[mid+1,r]的贡献
现在考虑如何更快的计算第3步?假设1,2步后,两个小区间内部变成了按y排序的,我们像归并一样的把两个小区间按y合并成一个大区间并得到[l,mid]对于[mid+1,r]的贡献.
先放一个nlog^2n的算法
bool Orz(node a,node b){ return a.x 再放一个好看的
struct node{ int x,y; int i;}o[60010],temp[60010];int ans[60010];int i,n;inline bool Orz(node a,node b){ return a.x==b.x?a.y r) { temp[tot]=o[a]; a++; } else { ans[o[b].i]+=a-l;//统计答案 temp[tot]=o[b]; b++; } } for(int i=l;i<=r;i++) o[i]=temp[i];}int main(){ n=read(); for(i=1;i<=n;i++) { o[i].x=read(); o[i].y=read(); o[i].i=i;//记录原始位置 } sort(o+1,o+1+n,Orz); CDQ(1,n);//调用分治 for(i=1;i<=n;i++) { write(ans[i]); putchar(10); }}
用CDQ A掉后可以去p2026交一下.可以看到两道题几乎一样,区别在于aibi的范围.但是离散化也能写啊QAQ
然后来看一个三位数点问题.
首先题目有些不一样了,假设随从i可以完爆f(i)个随从,本题询问的是f()=i的数量.
然后来做题.
为了继续套用CDQ的模板,我们可先按照x,y,z为第一,二,三关键字从小到大进行排序,这样可以保证任意区间[l,r]内的右区间不会对左区间产生贡献.为了O(r-l)的决策贡献,我们可以使得CDQ()两个子区间后,每个区间内部都是以y为第一关键字进行排序,然后继续按照归并排序的方法合并两个区间并计算贡献,具体计算方法也不一样了,并且y的单调性并不能保证z的单调性,我们需要树状数组了.
int i;int n,c[200010],ans[100010],cnt[100010];struct node{ int x,y,z; int i;}o[100010],temp[100010];inline int lowbit(int x){ return x&(-x);}inline void add(int x,int k){ while(x<=200000) { c[x]+=k; x+=lowbit(x); }}inline int ask(int x){ int sum=0; while(x) { sum+=c[x]; x-=lowbit(x); } return sum;}inline bool Orz(node a,node b){ return a.x==b.x?(a.y==b.y?(a.z==b.z?a.i r) { temp[tot]=o[a]; add(o[a].z,1); a++; } else { ans[o[b].i]+=ask(o[b].z); temp[tot]=o[b]; b++; } } while(a>l) { a--; add(o[a].z,-1); } for(tot=l;tot<=r;tot++) o[tot]=temp[tot];}int main(){ n=read();i=read(); for(i=1;i<=n;i++) { o[i].x=read(); o[i].y=read(); o[i].z=read(); o[i].i=i; } sort(o+1,o+1+n,Orz); CDQ(1,n); for(i=1;i<=n;i++) cnt[ans[i]]++; for(i=0;i 这个代码在洛谷上仍然过不了,在本校oj上倒是跑的很好.这说明我的代码还是很糙...//2019 2 20 14:37
不管了我们继续.
又有了一道CDQ.看一眼题目,是带修改的离线二维数点,如何来做呢?
先考虑如何读入.
当然是仁者见仁智者见智了.反正修改和询问是要平等的放在同一个数组(结构体)里的.我的方法是存在结构体里,并把询问拆成四个(假设x2>=x1,y2>=y1)sum(x2,y2)+sum(x1-1,y1-1)-sum(x2,y1-1)-sum(x1-1,y2).存一个i表示时间戳.并把询问的flag设为1,修改的flag设为0.
然后可以发现,一个区间查询sum(x,y)等价于 "查询所有时间戳小于它且x小于等于它且y小于等于它的flag=0的点的权和".这个和三维偏序好像啊,CDQ+树状数组A掉.
int i,T,tx1,tx2,ty1,ty2;int n,tot,c[500010];struct node{ int x,y; int i,sum; int flag;}o[800010],temp[800010];//操作数*4int lowbit(int x){ return x&(-x);}inline void add(int x,int k){ while(x<=n) { c[x]+=k; x+=lowbit(x); }}inline int ask(int x){ int sum=0; while(x) { sum+=c[x]; x-=lowbit(x); } return sum;}void CDQ(int l,int r){ if(l==r) return ; int mid=(l+r)/2,t=l,a=l,b=mid+1; CDQ(l,mid); CDQ(mid+1,r); for(;a<=mid||b<=r;t++) { if(a<=mid&&o[a].x<=o[b].x||b>r)//如果a可以用且a的x小于等于b的x或b不能用 { temp[t]=o[a]; if(!o[a].flag) add(o[a].y,o[a].sum); a++; } //else if(b<=r&&o[a].x>o[b].x||a>mid) else//如果b的x小于a的x或a不能用 { if(o[b].flag) o[b].sum+=ask(o[b].y); temp[t]=o[b]; b++; } } //从上面的if可以发现y的大小不会影响答案 for(a=l;a<=mid;a++) if(!o[a].flag) add(o[a].y,-o[a].sum); for(t=l;t<=r;t++) o[t]=temp[t]; return ;}inline bool Orz(node a,node b){ return a.i
继续继续.
看到题目,逆序对?我会树状数组!
动态的?n^2logn!
我瞎说的.
读入的时候进行一番操作,可以继续记录每个点的权值为x,位置为i,被删除的时间戳t(最后也没被删去的设为n+1好了).那么可以算每个点的答案为.x1>x&&i1<i&&t1<=t和x1<x&&i1>i&&t1<=t的数量.可以发现t1=t的那部分重复了.我们需要一个简单容斥.这样一处理就又是三维偏序了?我们可以自豪的说出:我会CDQ!
具体来说,大家可以先写个n^2的暴力,过样例后再调用CDQ写个暴力,再用CDQ写个更好的算法.
我也会用一晚上的时间搞出多个版本放在下面.
int i,tx;int n,m,c[100010];inline int lowbit(int x){ return x&(-x);}inline void add(int x,int k){ while(x<=n) { c[x]+=k; x+=lowbit(x); }}inline int ask(int x){ int sum=0; while(x) { sum+=c[x]; x-=lowbit(x); } return sum;}struct node{ int x,i,t;//权值,位置,时间 int ans;}o[100010],temp[100010];bool x_(node a,node b){ return a.x o[b].x&&o[a].i o[b].i) { o[a].ans++; } } //cout< < o[b].x&&o[a].i o[b].i) { o[m+1].ans++; } } } for(i=m;i;i--) { o[i].ans+=o[i+1].ans; } for(i=1;i<=m;i++) { cout< < int i,tx;int n,m,c[100010];inline int lowbit(int x){ return x&(-x);}inline void add(int x,int k){ while(x<=n) { c[x]+=k; x+=lowbit(x); }}inline int ask(int x){ int sum=0; while(x) { sum+=c[x]; x-=lowbit(x); } return sum;}struct node{ int x,i,t;//权值,位置,时间 int ans;}o[100010],temp[100010];int sum;bool x_(node a,node b){ return a.x o[b].x&&o[a].i o[b].i) o[a].ans++; }void two(int l,int r){ sort(o+1,o+1+n,t_); sort(o+l,o+r+1,x_); for(int a=l;a<=r;a++) { sum+=a-l-ask(o[a].i); add(o[a].i,1); } memset(c,0,sizeof(c));}int main(){ // freopen("123.in","r",stdin); n=read();m=read(); for(i=1;i<=n;i++) { o[i].x=read(); o[i].i=i; o[i].t=m+1; } sort(o+1,o+1+n,x_); for(i=1;i<=m;i++) { tx=read(); o[tx].t=i; } two(m+1,n); sort(o+1,o+1+n,t_); three(); sort(o+1,o+1+n,t_); o[m+1].ans=sum; for(i=m;i;i--) o[i].ans+=o[i+1].ans; for(i=1;i<=m;i++) cout< < int sum;bool x_(node a,node b){ return a.x b.x;}bool t_(node a,node b){ return a.t r) { o[a].ans+=b-mid-1-ask(o[a].i); temp[tot]=o[a]; a++; } else { add(o[b].i,1); temp[tot]=o[b]; b++; } for(b=mid+1;b<=r;b++) add(o[b].i,-1); for(tot=l;tot<=r;tot++) o[tot]=temp[tot];}void CDQ2(int l,int r){ if(l==r) return ; int mid=(l+r)/2,a=l,b=mid+1,tot=l; CDQ2(l,mid); CDQ2(mid+1,r); for(;a<=mid||b<=r;tot++) if(a<=mid&&o[a].x>o[b].x||b>r) { o[a].ans+=ask(o[a].i); temp[tot]=o[a]; a++; } else { add(o[b].i,1); temp[tot]=o[b]; b++; } for(b=mid+1;b<=r;b++) add(o[b].i,-1); for(tot=l;tot<=r;tot++) o[tot]=temp[tot];}void three(){ CDQ1(1,m); /*for(int a=1;a<=m;a++) for(int b=a+1;b<=m;b++) if(o[a].x>o[b].x&&o[a].i o[b].x&&o[a].i o[b].i) o[a].ans++;}void two(int l,int r){ sort(o+1,o+1+n,t_); sort(o+l,o+r+1,x_); for(int a=l;a<=r;a++) { sum+=a-l-ask(o[a].i); add(o[a].i,1); } memset(c,0,sizeof(c));}int main(){ freopen("123.in","r",stdin); n=read();m=read(); for(i=1;i<=n;i++) { o[i].x=read(); o[i].i=i; o[i].t=m+1; } sort(o+1,o+1+n,x_); for(i=1;i<=m;i++) { tx=read(); o[tx].t=i; } two(m+1,n); sort(o+1,o+1+n,t_); three(); sort(o+1,o+1+n,t_); o[m+1].ans=sum; for(i=m;i;i--) o[i].ans+=o[i+1].ans; for(i=1;i<=m;i++) cout< < #include#include #include #include #include #include #include #include #include #include
long long i,tx;long long n,m,c[100010];inline long long lowbit(long long x){ return x&(-x);}inline void add(long long x,long long k){ while(x<=n) { c[x]+=k; x+=lowbit(x); }}inline long long ask(long long x){ long long sum=0; while(x) { sum+=c[x]; x-=lowbit(x); } return sum;}struct node{ long long x,i,t;//权值,位置,时间 long long ans;}o[100010],temp[100010];long long sum;inline bool x_(node a,node b){ return a.x b.x;}inline bool t_(node a,node b){ return a.t r) { o[a].ans+=b-mid-1-ask(o[a].i); temp[tot]=o[a]; a++; } else { add(o[b].i,1); temp[tot]=o[b]; b++; } for(b=mid+1;b<=r;b++) add(o[b].i,-1); for(tot=l;tot<=r;tot++) o[tot]=temp[tot];}void CDQ2(long long l,long long r){ if(l==r) return ; long long mid=(l+r)/2,a=l,b=mid+1,tot=l; CDQ2(l,mid); CDQ2(mid+1,r); for(;a<=mid||b<=r;tot++) if(a<=mid&&o[a].x>o[b].x||b>r) { o[a].ans+=ask(o[a].i); temp[tot]=o[a]; a++; } else { add(o[b].i,1); temp[tot]=o[b]; b++; } for(b=mid+1;b<=r;b++) add(o[b].i,-1); for(tot=l;tot<=r;tot++) o[tot]=temp[tot];}void three(){ CDQ1(1,m); sort(o+1,o+1+n,t_); CDQ2(1,m); sort(o+1,o+1+n,t_); sort(o+1,o+1+m,x_); sort(o+1+m,o+n+1,x_); long long a=1,b=m+1; for(;a<=m||b<=n;) if(a<=m&&o[a].x n) { o[a].ans+=b-m-1-ask(o[a].i); a++; } else { add(o[b].i,1); b++; } memset(c,0,sizeof(c)); sort(o+1,o+1+m,_x); sort(o+1+m,o+1+n,_x); for(a=1,b=m+1;a<=m||b<=n;) if(a<=m&&o[a].x>o[b].x||b>n) { o[a].ans+=ask(o[a].i); a++; } else { add(o[b].i,1); b++; } sort(o+1,o+1+n,t_);}void two(long long l,long long r){ sort(o+1,o+1+n,t_); sort(o+l,o+r+1,x_); for(long long a=l;a<=r;a++) { sum+=a-l-ask(o[a].i); add(o[a].i,1); } memset(c,0,sizeof(c));}int main(){ n=read();m=read(); for(i=1;i<=n;i++) { o[i].x=read(); o[i].i=i; o[i].t=m+1; } sort(o+1,o+1+n,x_); for(i=1;i<=m;i++) { tx=read(); o[tx].t=i; } two(m+1,n); sort(o+1,o+1+n,t_); three(); sort(o+1,o+1+n,t_); o[m+1].ans=sum; for(i=m;i;i--) o[i].ans+=o[i+1].ans; for(i=1;i<=m;i++) { write(o[i].ans); putchar(10); }} 最终的版本实现方式:先二维偏序sort+树状数组解决(m,n]内的贡献记在sum里 ,最后给o[m+1].ans,并用两次三维偏序解决[1,n]内部的贡献,再跑一边归并计算出(m,n]对[1,n]的贡献.逆序跑一遍后缀和后正序输出.