树套树【bzoj3262】陌上花开

【bzoj3262】陌上花开

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的每级花的数量。*/

//树套树 cdq分治不会

//卡时函数大视野竟然不认，给我报了n遍RE，气死我了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define M 5000005
using namespace std;
struct shu
{
int x,y,z;
}a[100005];
int n,m,sum[100005],ans[100005],sz,root[200005],w[M],v[M],sz1[M],lr[M],rr[M],rou[M];
int tmp;
bool cmp(shu a1,shu a2)
{
if(a1.x==a2.x&&a1.y==a2.y)
   return a1.z<a2.z;
if(a1.x==a2.x)
   return a1.y<a2.y;
return a1.x<a2.x;
}
void update(int a1)
{
sz1[a1]=sz1[lr[a1]]+sz1[rr[a1]]+w[a1];
}
void zuo(int &a1)
{
int t=lr[a1];
lr[a1]=rr[t];
rr[t]=a1;
update(a1);
update(t);
a1=t;
}
void you(int &a1)
{
int t=rr[a1];
rr[a1]=lr[t];
lr[t]=a1;
update(a1);
update(t);
a1=t;
}
void jiaa(int &a1,int a2)
{
if(a1==0)
   {
   sz++;
   a1=sz;
   v[a1]=a2;
   sz1[a1]=1;
   w[a1]=1;
   rou[a1]=rand();
   return;
   }
sz1[a1]++;
if(v[a1]==a2)
   {
   w[a1]++;
   return;
   }
if(v[a1]>a2)
   {
   jiaa(lr[a1],a2);
   if(rou[lr[a1]]<rou[a1])
      zuo(a1);
   }
else
   {
   jiaa(rr[a1],a2);
   if(rou[rr[a1]]<rou[a1])
      you(a1);
   }
}
void jia(int a1,int a2)
{
for(;a1<=m;a1+=(a1&(-a1)))
   jiaa(root[a1],a2);
}
void askk(int a1,int a2)
{
if(a1==0)
   return;
if(v[a1]==a2)
    {
    tmp+=w[a1]+sz1[lr[a1]];
    return;
    }
if(v[a1]>a2)
   askk(lr[a1],a2);
else
   {
   tmp+=w[a1]+sz1[lr[a1]];
   askk(rr[a1],a2);
   }
return;
}
void ask(int a1,int a2)
{
for(;a1;a1-=(a1&(-a1)))
   askk(root[a1],a2);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
   scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
   if(a[i].y==a[i+1].y&&a[i].z==a[i+1].z&&a[i].x==a[i+1].x&&i!=n)
     sum[i+1]+=sum[i]+1;
   else
     {
     tmp=0;
     ask(a[i].y,a[i].z);
     ans[tmp]+=sum[i]+1;
  }
   jia(a[i].y,a[i].z);
     }
for(int i=0;i<n;i++)
   printf("%d ",ans[i]);
    return 0;
}