CDQ分治

学长课件在文件。

定义和正确性看课件。

主要总结下CDQ可做的题

特征：

限制多，三位偏序等
可以离线
复杂度$O(nlog^2n)$ 可过

三维偏序：要求a的三个变量都大于（等于）b的三个变量

对于二维偏序问题，我们可以对第一维排序，然后用树状数组维护第二维。

对于三维偏序，我们可以用cdq第一维归并第二维树状数组第三维

提醒自己：cmp函数最好拆开写！　　第二维最好是时间！

三维偏序板子题，但是我头铁+失了智没看板子硬刚了一上午

主要是重复的没考虑全，去重的原因

对于a b c完全相同的花，直接扫一边去重（最好用两个数组，一个数组贼玄学主要是我菜），记得把siz累加

然后就可以愉快的cdq了，最后统计答案对于i的等级要加上和它重复的个数（不包括i自己）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 #define reg register
  6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
  7 using namespace std;
  8 inline int read();
  9 const int N=200005;
 10 int n,maxk;
 11 bool mark[N];
 12 struct FW{
 13     int id,a,b,c,siz;
 14 }tf[N],f[N],q[N];
 15 bool cmp1(FW x,FW y)
 16 {
 17     return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;
 18 }
 19 bool cmp2(FW x,FW y)
 20 {
 21     return x.a==y.a&&x.b==y.b&&x.c==y.c;
 22 }
 23 int t[N],ans[N],pt[N];
 24 void add(int x,int w)
 25 {
 26     while(x<=maxk)
 27     {
 28         t[x]+=w;
 29         x+=(x&-x);
 30     }
 31 }
 32 int ask(int x)
 33 {
 34     int ans=0;
 35     while(x)
 36     {
 37         ans+=t[x];
 38         x-=(x&-x);
 39     }
 40     return ans;
 41 }
 42 void cdq(int l,int r)
 43 {
 44     if(l==r) return;
 45     int mid=(l+r)>>1;
 46     int pl=l,pr=mid+1,p=l;
 47     cdq(l,mid); cdq(mid+1,r);
 48     while(pl<=mid&&pr<=r)
 49     {
 50         if(f[pl].b<=f[pr].b) q[p++]=f[pl++];
 51         else q[p]=f[pr++],mark[p++]=1;
 52     }
 53     while(pl<=mid) q[p++]=f[pl++];
 54     while(pr<=r) q[p]=f[pr++],mark[p++]=1;
 55     F(i,l,r)
 56     {
 57         if(mark[i]) ans[q[i].id]+=ask(q[i].c);
 58         else add(q[i].c,q[i].siz);
 59     }
 60     F(i,l,r)
 61     {
 62         if(mark[i]) mark[i]=0;
 63         else add(q[i].c,-q[i].siz);
 64         f[i]=q[i];
 65     }
 66 }
 67 int main()
 68 {
 69     n=read(); maxk=read();
 70     F(i,1,n)
 71     {
 72         tf[i].id=i;
 73         tf[i].siz=1;
 74         tf[i].a=read(); tf[i].b=read(); tf[i].c=read();
 75     }
 76     sort(tf+1,tf+n+1,cmp1);
 77     int cnt=0;
 78     f[++cnt]=tf[1];
 79     F(i,2,n)
 80     {
 81         if(cmp2(f[cnt],tf[i]))
 82         {
 83             f[cnt].siz+=tf[i].siz;
 84         }
 85         else
 86         {
 87             f[++cnt]=tf[i];
 88         }
 89     }
 90     F(i,1,cnt) f[i].id=i;
 91     cdq(1,cnt);
 92     F(i,1,cnt) pt[ans[f[i].id]+f[i].siz-1]+=f[i].siz;
 93     F(i,0,n-1) printf("%d
",pt[i]);
 94     return 0;
 95 }
 96 inline int read()
 97 {
 98     int x=0;
 99     char tc=getchar();
100     while(tc<'0'||tc>'9') tc=getchar();
101     while(tc>='0'&&tc<='9')
102     {
103         x=x*10+tc-48;
104         tc=getchar();
105     }
106     return x;
107 }

View Code

如果我们把所有操作附上一个时间戳

那么我们发现能对一个查询（t1,x1,y1）产生贡献的修改必须是（t2,x2,y2）其中$t2 leq t1 ,x2 leq x1 ,y2 leq y1$

然后就转换成了三维偏序问题。

对于查询的话要简单容斥下，拆成四个原点到(x,y)的查询，所以结构体数组一定要开够

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 #define reg register
  6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
  7 using namespace std;
  8 inline int read();
  9 const int N=200005,W=2000005;
 10 int s,n,now,tot;
 11 struct OPT{
 12     int opt,_time,id;
 13     int x,y,w;
 14 }t[N],q[N];
 15 int tr[W],res[N];
 16 bool mark[N];
 17 bool cmp(OPT a,OPT b)
 18 {
 19 //    a._time==b._time?(a.x==b.x?(a.y<b.y):(a.x<b.x)):(a._time<b._time);
 20     if(a._time!=b._time) return a._time<b._time;
 21     if(a.x!=b.x) return a.x<b.x;
 22     return a.y<b.y;
 23 }
 24 void build(int opt,int id,int x,int y,int w)
 25 {
 26     t[++now].opt=opt;
 27     t[now].x=x;
 28     t[now].y=y;
 29     t[now].w=w;
 30     t[now]._time=now;
 31     t[now].id=id;
 32 }
 33 void add(int x,int w)
 34 {
 35     while(x<=n)
 36     {
 37         tr[x]+=w;
 38         x+=(x&-x);
 39     }
 40 }
 41 int ask(int x)
 42 {
 43     int ans=0;
 44     while(x)
 45     {
 46         ans+=tr[x];
 47         x-=(x&-x);
 48     }
 49     return ans;
 50 }
 51 void cdq(int l,int r)
 52 {
 53     if(l==r) return;
 54     int mid=(l+r)>>1;
 55     cdq(l,mid); cdq(mid+1,r);
 56     int pl=l,pr=mid+1,p=l;
 57 //    printf("L=%d R=%d
",l,r);
 58     while(pl<=mid&&pr<=r)
 59     {
 60         if(t[pl].x<=t[pr].x)
 61         {
 62             q[p]=t[pl++];
 63             mark[p++]=1;        //左边的
 64         }
 65         else
 66         {
 67             q[p++]=t[pr++];
 68         }
 69     }
 70     while(pl<=mid)
 71     {
 72         q[p]=t[pl++];
 73         mark[p++]=1;
 74     }
 75     while(pr<=r) q[p++]=t[pr++];
 76     F(i,l,r)
 77     {
 78 //        printf("%d ",q[i].y);
 79         if(mark[i]&&q[i].opt==1)
 80         {
 81             add(q[i].y,q[i].w);        //q[i].w!!!!!!!!!!!!!!!
 82         }
 83         else if(!mark[i]&&q[i].opt==2)
 84         {
 85             res[q[i].id]+=q[i].w*ask(q[i].y);
 86 //            printf("w=%d
",q[i].id);
 87         }
 88     }
 89 //    printf("
");
 90 //    puts("");
 91     F(i,l,r)
 92     {
 93 //        printf("%d ",q[i]._time);
 94         if(mark[i]&&q[i].opt==1) add(q[i].y,-q[i].w);
 95         mark[i]=0;
 96         t[i]=q[i];
 97     }
 98 //    puts("");
 99 }
100 int main()
101 {
102 //    freopen("data.in","r",stdin);
103     s=read(); n=read();
104     int opt,x1,y1,x2,y2;
105     while(scanf("%d",&opt)==1&&opt!=3)
106     {
107         if(opt==1)
108         {
109             x1=read(); y1=read(); x2=read();
110             build(1,0,x1,y1,x2);
111         }
112         else
113         {
114             x1=read(); y1=read(); x2=read(); y2=read();
115             build(2,++tot,x2,y2,1);
116             build(2,tot,x2,y1-1,-1);
117             build(2,tot,x1-1,y2,-1);
118             build(2,tot,x1-1,y1-1,1);
119         }
120     }
121     sort(t+1,t+now+1,cmp);
122     cdq(1,now);
123     F(i,1,tot) printf("%d
",res[i]);
124     return 0;
125 }
126 inline int read()
127 {
128     int x=0;
129     char tc=getchar();
130     while(tc<'0'||tc>'9') tc=getchar();
131     while(tc>='0'&&tc<='9')
132     {
133         x=x*10+tc-48;
134         tc=getchar();
135     }
136     return x;
137 }

View Code

偷偷告诉你这题我s忘了用但A了

熟悉的数据范围。

曼哈顿距离带绝对值。

但是我们可以对整个坐标系进行翻转的骚操作。

然后依然是三维偏序问题。

but注意，这题要特判

如果树状数组返回0，说明从(x,y)到假想原点没有其他点，然后我们就把该点与假原点的曼哈顿距离计入了答案。。。所以如果返回0，直接-inf或者不更新ans

and树状数组逢0必死，记得坐标++

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 #define reg register
  6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
  7 using namespace std;
  8 inline int read();
  9 const int N=1000005;
 10 int n,m,now,cnt,mx,my;
 11 struct OPT{
 12     int opt,_time,id;
 13     int x,y;
 14 }f[N],q[N];
 15 int t[1000005],res[700005];
 16 bool mark[N];
 17 bool cmp(OPT a,OPT b)
 18 {
 19     if(a._time!=b._time) return a._time<b._time;
 20     if(a.x!=b.x) return a.x<b.x;
 21     return a.y<b.y;
 22 }
 23 void build(int opt,int id,int x,int y)
 24 {
 25     f[++now].opt=opt;
 26     f[now].id=id;
 27     f[now].x=x;
 28     f[now].y=y;
 29     f[now]._time=now;
 30 }
 31 void clear(int x)
 32 {
 33     while(x<=my)
 34     {
 35         t[x]=0;
 36         x+=(x&-x);
 37     }
 38 }
 39 void upd(int x,int w)
 40 {
 41     while(x<=my)
 42     {
 43         t[x]=max(t[x],w);
 44     //    printf("hah %d %d
",t[x],w);
 45         x+=(x&-x);
 46     }
 47 }
 48 int ask(int x)
 49 {
 50     int ans=0;
 51     while(x)
 52     {
 53         ans=max(ans,t[x]);
 54     //    printf("hah %d %d
",t[x],ans);
 55         x-=(x&-x);
 56     }
 57     return ans;
 58 }
 59 void cdq(int l,int r)
 60 {
 61     if(l==r) return;
 62     int mid=(l+r)>>1;
 63     cdq(l,mid); cdq(mid+1,r);
 64 //    printf("L=%d R=%d
",l,r);
 65     int pl=l,pr=mid+1,p=l;
 66     while(pl<=mid&&pr<=r)
 67     {
 68         if(f[pl].x<=f[pr].x) q[p]=f[pl++],mark[p++]=1;
 69         else q[p++]=f[pr++];
 70     }
 71     while(pl<=mid) q[p]=f[pl++],mark[p++]=1;
 72     while(pr<=r) q[p++]=f[pr++];
 73     F(i,l,r)
 74     {
 75         if(mark[i]&&q[i].opt==1) upd(q[i].y,q[i].x+q[i].y);
 76         else if(!mark[i]&&q[i].opt==2)
 77         {
 78             int ta=ask(q[i].y);
 79             if(ta==0) ta=-0x3f3f3f3f;
 80             res[q[i].id]=min(res[q[i].id],q[i].x+q[i].y-ta);//,printf("tans=%d
",q[i].x+q[i].y-ask(q[i].y));
 81         }
 82     }
 83 //    printf("ddd   %d
",ask(100));
 84     F(i,l,r)
 85     {
 86         if(mark[i]&&q[i].opt==1) clear(q[i].y);
 87         mark[i]=0;
 88         f[i]=q[i];
 89     }
 90 }
 91 int main()
 92 {
 93 //    freopen("data.in","r",stdin);
 94 //    freopen("data.out","w",stdout);
 95     memset(res,0x3f,sizeof(res));
 96     n=read(); m=read();
 97     int opt,a,b;
 98     F(i,1,n)
 99     {
100         a=read()+1; b=read()+1;
101         mx=max(mx,a);
102         my=max(my,b);
103         build(1,0,a,b);
104     }
105     F(i,1,m)
106     {
107         opt=read();
108         a=read()+1;
109         b=read()+1;
110         mx=max(mx,a);
111         my=max(my,b);
112         if(opt==1) build(1,0,a,b);
113         else build(2,++cnt,a,b);
114     }
115     ++mx; ++my;
116     sort(f+1,f+now+1,cmp);
117     cdq(1,now);
118 
119     F(i,1,now) f[i].x=mx-f[i].x;
120     sort(f+1,f+now+1,cmp);
121     cdq(1,now);
122 
123     F(i,1,now)
124     {
125         f[i].x=mx-f[i].x;
126         f[i].y=my-f[i].y;
127     }
128     sort(f+1,f+now+1,cmp);
129     cdq(1,now);
130 
131     F(i,1,now) f[i].x=mx-f[i].x;
132     sort(f+1,f+now+1,cmp);
133     cdq(1,now);
134 
135     F(i,1,cnt) printf("%d
",res[i]);
136     return 0;
137 }
138 inline int read()
139 {
140     int x=0;
141     char tc=getchar();
142     while(tc<'0'||tc>'9') tc=getchar();
143     while(tc>='0'&&tc<='9')
144     {
145         x=x*10+tc-48;
146         tc=getchar();
147     }
148     return x;
149 }

View Code

CDQ分治

A. 陌上花开

B. Mokia

C. 天使玩偶