本来几天前就该记录的东西，硬生生被我拖到了现在，太懒了。。。
在cdq学习时，二维偏序已经解决了，无非就是先sort使第一维有序，然后再用cdq或者数据结构处理第二维。而三维偏序的时候呢，大佬的做法好像有树套树之类的，但是我不会，所以我选择cdq。
大体的思路很简单，首先也是先使第一维有序，然后cdq把第二维由小到大合并，这时再套个线段树或者树状数组处理第三维。来几题做一下
题目大意：一个花园里有n棵数，然后有m次询问，每次询问一个矩形里有多少颗树。
把原有的树视为更新操作，然后每个查询分为加上（0,0）到（x1-1,y1-1）范围内的树，减去（0,0）到（x1-1,y2）范围内的树，减去（0,0）到（x2,y1-1）范围内的树，加上（0,0）到（x2,y2）范围内的树，这样就可以处理一个二维前缀和，然后用cdq分治理套树状数组处理y轴
1 #include2 #include 3 #define lowb(x) (x&(-x)) 4 using namespace std; 5 const int N=500118,M=500118,Y=10000118,Q=(M<<2)+N;//每个查询分4个 6 struct Nop{ 7 int x,y,op,w,id; 8 friend bool operator < (const Nop &n1,const Nop &n2){ 9 return n1.x==n2.x ? n1.op >1; 50 cdq(l,m); 51 cdq(m+1,r); 52 int i=l,j=m+1,k=l; 53 while(i<=m&&j<=r) 54 { 55 if(P[i]
当然，这题很明显是个二维偏序问题，因为树本身都存在了，没有什么更新操作，直接离线树状数组处理就行。
1 #include2 #include 3 #define lowb(x) (x&(-x)) 4 using namespace std; 5 const int N=500118,M=500118,Y=10000118,Q=(M<<2)+N; 6 struct Nop{ 7 int x,y,op,w,id; 8 friend bool operator < (const Nop &n1,const Nop &n2){ 9 return n1.x==n2.x ? n1.op
题目大意：维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
S值并没有实际作用忽略就好。这题就不行像上面那题单纯的离线然后树状数组维护就行了，因为是有着一个更新的存在，不同的查询前面的更新是不一样的。所以就是我们大体的思路，把每个操作视为（操作时间，x轴，y轴）这样的带有附加消息的三维有序对，这样第一维已经有序了，我们就只需要把x轴cdq分治处理，然后y轴有树状数组处理，查询也就是维护个二维的前缀和。
1 #include2 #include 3 #define lowb(x) (x&(-x)) 4 using namespace std; 5 const int N=160118,M=10118,Y=2001108,Q=(M<<2)+N; 6 struct Nop{ 7 int x,y,op,w,id; 8 friend bool operator < (const Nop &n1,const Nop &n2){ 9 return n1.x==n2.x ? n1.op >1; 50 cdq(l,m); 51 cdq(m+1,r); 52 int i=l,j=m+1,k=l; 53 while(i<=m&&j<=r) 54 { 55 if(P[i]
题目大意：有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
这就是个三维偏序的问题了，没有什么更新和查询就是（s,c,m）的三维有序对求顺序对，我们同样是让sort按s由小到大，s相同按c排，c相同按m排的cmp使得第一维s有序，然后cdq分治处理第二维c，树状数组维护第三维m，最后提交，好的，wrong了。因为一个重要的点，,两朵花可能有同样的属性，如果我们不去重的话，那么相同的属性的话，因为它们的顺序不同造成它们的等级不同。所以我们把属性相同的归为一类，然后统计这一类有多少个，然后作为树状数组维护的权值维护就行，有个小细节就是当分到最小的子区间也就是只有一朵花时，它的等级应该还得提升它的权值-1，因为那些和它属性相同的合为一类了，具体的就看代码注释。
1 #include2 #include 3 #define lowb(x) (x&(-x)) 4 using namespace std; 5 const int N=100118,K=200118; 6 struct Flower{ 7 int id,s,c,m,w; 8 friend bool operator == (const Flower &f1,const Flower &f2){ 9 return f1.s==f2.s&&f1.m==f2.m&&f1.c==f2.c; 10 } 11 }F[N],temp[N]; 12 int fn,ans[N]={ 0},rank[N]={ 0},summ[K]={ 0}; 13 //ans[i]保存编号为i的花的等级，也就是属性小于或等于它的数目 14 bool cmp(const Flower &f1,const Flower &f2){ 15 return f1.s==f2.s ? (f1.c==f2.c ? f1.m >1; 56 cdq(l,mid); 57 cdq(mid+1,r); 58 int i=l,j=mid+1,k=l; 59 while(i<=mid&&j<=r) 60 { 61 if(F[i].c<=F[j].c) 62 { 63 updata(F[i].m,F[i].w); 64 temp[k++]=F[i++]; 65 } 66 else 67 { 68 ans[F[j].id]+=getsum(F[j].m); 69 temp[k++]=F[j++]; 70 } 71 } 72 while(i<=mid) 73 temp[k++]=F[i++]; 74 while(j<=r) 75 { 76 ans[F[j].id]+=getsum(F[j].m); 77 temp[k++]=F[j++]; 78 } 79 for(i=l;i<=r;i++) 80 { 81 clear(F[i].m); 82 F[i]=temp[i]; 83 } 84 } 85 int main() 86 { 87 int n,k; 88 while(~scanf("%d%d",&n,&k)) 89 { 90 for(int i=0;i