[CDQ分治]三维偏序
我不是柳橙汁
2017-12-25 20:24:40
听过了某巘大佬的教导，我决定学习下CDQ分治。
所以从上上个星期卡到现在。
这是某巘大佬的代码，我对其做了注释。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define neko 1000010
#define mid ((l+r)>>1)
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-(i)))
static struct node{
int a,b,c,cnt,id,ans;
bool operator == (const node &x)const{return a==x.a&&b==x.b&&c==x.c;}
}q[neko],tmp[neko];
static int n,maximum,p,a[neko],b[1000010],Ans[1000010];
bool cmpa(node x,node y){return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;}
inline void read(int &x){//读优
#ifndef ONLINE_JUDGE
char c=getchar();x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
#else
static const int BUFSIZE=1048576;
static char buf[BUFSIZE];
static char *bufnow=buf;
static char *bufmax=buf;
if(bufnow==bufmax){
bufmax=buf+fread(buf,1,BUFSIZE,stdin);
bufnow=buf;
}int c=*bufnow++;
while(!isdigit(c)){
if(bufnow==bufmax){
bufmax=buf+fread(buf,1,BUFSIZE,stdin);
bufnow=buf;
}c=*bufnow++;
}x=0;
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^'0');
if(bufnow==bufmax){
bufmax=buf+fread(buf,1,BUFSIZE,stdin);
bufnow=buf;
}c=*bufnow++;
}
#endif
}
void add(int x,int y){//修改操作
for(;x<=maximum;x+=x&-x)
b[x]+=y;
}
int query(int x){//询问操作
int sum=0;
for(;x;x-=x&-x)
sum+=b[x];
return sum;
}
inline bool cmp(node a,node b){return a.id<b.id;}
void cdq(int l,int r){//分治主体，二维CDQ
if(l==r)return;
cdq(l,mid),cdq(mid+1,r);//分治
int i=l,j=l,k=mid+1;
while(j<=mid&&k<=r){
if(q[j].b<=q[k].b)tmp[i++]=q[j++];
else tmp[i++]=q[k++];
}
while(j<=mid)tmp[i++]=q[j++];
while(k<=r)tmp[i++]=q[k++];//对[l,r]区间排序给tmp数组
int num=0;
j=mid+1;
f(i,l,r){//三维树状数组
q[i]=tmp[i];
if (q[i].id<=mid) add(q[i].c,q[i].cnt);//如果他原来是左边的，表示他一定会影响到右边的，然后左边的又在前面的分治中处理完了，所以不需要处理
else q[i].ans+=query(q[i].c);//每读到一个右边的就累加答案
}
f(i,l,r)
if(q[i].id<=mid)//清回去
add(q[i].c,-q[i].cnt);
}
int main(){
int x;
read(n),read(maximum);
f(i,1,n) read(q[i].a),read(q[i].b),read(q[i].c);
td::sort(q+1,q+n+1,cmpa);//一维排序
f(i,1,n){
if (q[i]==q[i-1]) q[p].cnt++;
else q[++p]=q[i],q[p].cnt=1,q[p].id=p;
}
cdq(1,p);
f(i,1,p) Ans[q[i].ans+q[i].cnt-1]+=q[i].cnt;//题目要求输出
f(i,0,n-1) printf("%d\n",Ans[i]);
return 0;
}
```
我自己就学着打了一份并AC了。
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
#define mid (l+r>>1)
struct node{
long long a,b,c,cnt,id,ans;
bool operator == (const node &x)const{
return a==x.a&&b==x.b&&c==x.c;
}
}q[100010],tmp[100010];
long long n,maxn,p,ans[200010],tree[200010];
inline long long v_in(){
char ch=getchar();
long long sum=0,f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
sum=(sum<<1)+(sum<<3)+(ch^48);
ch=getchar();
}
return sum*f;
}
inline bool cmpa(const node &x,const node &y){
return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;
}
inline void add(long long now,long long c){
while (now<=maxn){
tree[now]+=c;
now+=now&-now;
}
}
inline long long query(long long now){
long long sum=0;
while (now){
sum+=tree[now];
now-=now&-now;
}
return sum;
}
inline void cdq(long long l,long long r){
if (l==r) return;
cdq(l,mid),cdq(mid+1,r);
long long i=l,j=mid+1,k=l;
while (i<=mid&&j<=r){
if (q[i].b<=q[j].b) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while (i<=mid) tmp[k++]=q[i++];
while (j<=r) tmp[k++]=q[j++];
k=mid+1;
for (register long long i=l;i<=r;i++){
q[i]=tmp[i];
if (q[i].id<=mid) add(q[i].c,q[i].cnt);
else q[i].ans+=query(q[i].c);
}
for (register long long i=l;i<=r;i++)
if (q[i].id<=mid) add(q[i].c,-q[i].cnt);
}
int main(){
n=v_in();
maxn=v_in();
for (register long long i=1;i<=n;i++){
q[i].a=v_in();
q[i].b=v_in();
q[i].c=v_in();
}
sort(q+1,q+n+1,cmpa);
for (register long long i=1;i<=n;i++){
if (q[i]==q[i-1]) q[p].cnt++;
else q[++p]=q[i],q[p].cnt=1,q[p].id=p;
}
cdq(1,p);
for (register long long i=1;i<=p;i++) ans[q[i].ans+q[i].cnt-1]+=q[i].cnt;
for (register long long i=0;i<n;i++) printf("%lld\n",ans[i]);
return 0;
}
```
其实就是先分后治，归并不过是CDQ的一种罢了。
当然我之后还会去做动态逆序对，以此巩固。