Description

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性

Output

包含N行，分别表示评级为0...N-1的每级花的数量。

 

Sample Input

10 3

3 3 3

2 3 3

2 3 1

3 1 1

3 1 2

1 3 1

1 1 2

1 2 2

1 3 2

1 2 1

Sample Output

3

1

3

0

1

0

1

0

0

1

——————————————————————————

CDQ分治不那么裸的题吧……？可能我菜。

（事实证明三维偏序是CDQ最常见的表现形式……我是真的菜）

首先如果我们做过的话， 那这题的思路就不难想：我们对一个维度进行排序，对于另一个维度树状数组统计比它晓得个数有几个，那我们就能够确定它的等级。

不幸的是，这题有三个维度，排掉一个还剩两个，总不能树状数组套树状数组吧（我也不会写啊……）

这时候我们就想到了神奇的CDQ分治，但是这并没有查询和修改操作啊……

好的我们开始对题目重新理解一下！

首先定义我们的修改操作就是往树状数组里添加/删除节点，我们的查询操作就是查询该点的等级。

那么对于一维肯定是要排序的，在那之后我们把根据一维排好的序当做查询/修改的时间，于是我们就神奇的变成了：先询问（该点等级），再修改（将节点插入）的在线问题。

那么CDQ就可以上了！我们对每个区间的节点的二维排序之后套树状数组查三维即可。

PS1：CDQ具体做法：我们每次添加区间前一半的点，后一半进行查询（原因不好用语言表达，大致意思为一个点到区间前端的这段区间可以由若干个CDQ区间的整个前半组成）

PS2：本题还有一个坑点，即相同的点也算是比自己丑（……），而树状数组对于一串相同的点的查询，只有最后一个点的答案正确，其他的点的答案分别为：倒数第二与ans差1，倒数第三与ans差2……所以我们预处理一下即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=100001;inline int read(){ int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct flower{ int x; int y; int z; int num; int ans;}a[N],b[N];int ans[N],tree[2*N],n,k;bool cmp(flower a,flower b){ return (a.x
            
             
              
               0;i-=lowbit(i))res+=tree[i]; return res;}void cdq(int l,int r){ if(l>=r)return; int mid=(l+r)>>1; cdq(l,mid);cdq(mid+1,r); for(int i=l,j=l,p=mid+1;i<=r;i++){ if(j<=mid&&(p>r||a[j].y<=a[p].y))b[i]=a[j++]; else b[i]=a[p++]; } for(int i=l;i<=r;i++){ a[i]=b[i]; if(a[i].num<=mid)add(a[i].z,1); else a[i].ans+=query(a[i].z); } for(int i=l;i<=r;i++)if(a[i].num<=mid)add(a[i].z,-1); return;}int main(){ n=read(); k=read(); for(int i=1;i<=n;i++){ a[i].x=read(); a[i].y=read(); a[i].z=read(); } sort(a+1,a+n+1,cmp); flower t;int cnt=1; for(int i=n;i>=1;i--){ if(same(t,a[i])){ a[i].ans+=cnt; cnt++; } else{ t=a[i]; cnt=1; } } for(int i=1;i<=n;i++)a[i].num=i; cdq(1,n); for(int i=1;i<=n;i++)ans[a[i].ans]++; for(int i=0;i