陌上花开（三维偏序）

其实还是比较好理解的qaq。。。

先来看题：

题目描述

有

对于

输入输出格式

输入格式：

第一行两个整数

之后

输出格式：

输出

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

作为CDQ的一道板子题，我们先来明确一下到底什么是CDQ？

CDQ通俗一点说就是三句话：

1.递归前一半

2.判断前一半对于后一半的影响

3.递归后一半

那么我们来看这道经典的三维偏序题，说一下大体的思路：

首先我们可以以x作为第一关键字进行排序，（y和z作为次要关键字），这样我们就可以保证从左到右是以x单调递增的。

然后我们将这个区间一分为二，分别对于每一个序列以y作为第一关键字排序，这样一来我们得到的两个序列拥有以下的性质：

1.左序列的任意x值都小于右序列的任意x值

2.每一个序列里的y值都是单调递增的

最后我们分别在序列头和序列中点设定两个指针j和i，对于每一个i，j都从头开始枚举，将j对应的y小于i对应的y的j加入树状数组中，最后只要判断z值是否满足条件就可以了。

当然，这道题还有一些小细节：

1.由于原序列可能会有重复的数，我们要先进行去重，并储存每一个数都代表了几个相同的数。

2.每一次i的增加都要清空树状数组，只要加上之前加的相反数就可以了。

好像也就这些了。。。

最后，附上本题代码：

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define maxn 100010
  4 #define maxk 200010
  5 using namespace std;
  6 struct node
  7 {
  8     int x,y,z,ans,w;
  9 };
 10 node a[maxn],b[maxn];
 11 int n,cnt[maxk];
 12 int k,z;
 13 bool cmp1(node u,node v)
 14 {
 15     if(u.x==v.x)
 16     {
 17         if(u.y==v.y)
 18             return u.z<v.z;
 19         return u.y<v.y;
 20     }
 21     return u.x<v.x;
 22 }
 23 bool cmp2(node u,node v)
 24 {
 25     if(u.y==v.y)
 26         return u.z<v.z;
 27     return u.y<v.y;
 28 }
 29 struct TREE
 30 {
 31     int tre[maxk],kk;
 32     int lowbit(int x)
 33     {
 34         return x&(-x);
 35     }
 36     int ask(int i)
 37     {
 38         int ans=0;
 39         for(; i; i-=lowbit(i))
 40         {
 41             ans+=tre[i];
 42         }
 43         return ans;
 44     }
 45     void add(int i,int k)
 46     {
 47         for(; i<=kk; i+=lowbit(i))
 48         {
 49             tre[i]+=k;
 50         }
 51     }
 52 } t;
 53 void cdq(int l,int r)
 54 {
 55     if(l==r)
 56     {
 57         return;
 58     }
 59     int mid=(l+r)>>1;
 60     cdq(l,mid);
 61     cdq(mid+1,r);
 62     sort(a+l,a+mid+1,cmp2);
 63     sort(a+mid+1,a+r+1,cmp2);//可能大家会有一些疑问，但是这个就是指针的用法，上面的是从l到mid，下面是mid+1到r
 64     int i=mid+1,j=l;
 65     while(i<=r)
 66     {
 67         while(a[j].y<=a[i].y && j<=mid)
 68         {
 69             t.add(a[j].z,a[j].w);
 70             j++;
 71         }
 72         a[i].ans+=t.ask(a[i].z);
 73         i++;
 74     }
 75     for(i=l; i<j; i++)
 76     {
 77         t.add(a[i].z,-a[i].w);
 78     }
 79 }
 80 int main()
 81 {
 82     scanf("%d%d",&z,&k);//z是数量，k是最大属性值
 83     t.kk=k;//设定上限，t是维护的树状数组
 84     for(int i=1; i<=z; i++)
 85     {
 86         scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);//
 87     }
 88     sort(b+1,b+z+1,cmp1);//排序
 89     int c=0;
 90     for(int i=1; i<=z; i++)
 91     {
 92         c++;
 93         if(b[i].x!=b[i+1].x || b[i].y!=b[i+1].y || b[i].z!=b[i+1].z )
 94             a[++n]=b[i],a[n].w=c,c=0;
 95     }//去重
 96     cdq(1,n);//cdqaq
 97     for(int i=1; i<=n; i++)
 98     {
 99         cnt[a[i].ans+a[i].w-1]+=a[i].w;//这个地方不太好理解：cnt【x】就是储存f【i】= x的个数，x就等于i的答案加上它重复的个数（可以取等）减去本身

100     }
101     for(int i=0; i<z; i++)
102     {
103         printf("%d
",cnt[i]);
104     }
105     return 0;
106 }