反正就是裸題。。。。先是去重 然後按x排序降一維 在根據y來插排 最後z在樹狀數組上查詢修改就好了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char c;
inline void read(int &a)
{
a=0;do c=getchar();while(c<'0'||c>'9');
while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();
}
struct O
{
int x,y,z,ans,time;
bool del;
inline friend bool operator <(O a,O b)
{return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.z<b.z);}
}Line[100001];
int n;
int level[100001];
int BIT[600001];
int base;
inline int lowbit(int a){return a&-a;}
inline int Query(int a){
int res=0;
for(int i=a;i;i^=lowbit(i))
res+=BIT[i];
return res;}
inline void Add(int a,int delta){for(int i=a;i<=base;i+=lowbit(i))BIT[i]+=delta;}
inline void Div(int L,int R)
{
if(L^R)
{
int Mid=(L+R)>>1;
Div(L,Mid),Div(Mid+1,R);
int i,j=L,t;
for(i=Mid+1;i<=R;i++)
{
while(Line[j].y<=Line[i].y&&j<=Mid)
{
Add(Line[j].z,Line[j].time);
j++;
}
Line[i].ans+=Query(Line[i].z);
}
j--;
while(j>=L)Add(Line[j].z,-Line[j].time),j--;
O S[R-L+2];
i=Mid+1,j=L,t=0;
while(i<=R&&j<=Mid)
if(Line[i].y<=Line[j].y)S[++t]=Line[i++];
else S[++t]=Line[j++];
while(i<=R)S[++t]=Line[i++];
while(j<=Mid)S[++t]=Line[j++];
for(i=1;i<=t;i++)
Line[L+i-1]=S[i];
}
}
O Swap[1000001];
inline void print(int &a)
{
if(a<10){putchar('0'+a),putchar('\n');return;}
long long base=1;
while(base<=a)base=(base<<3)+(base<<1);
base/=10;
while(base)putchar('0'+a/base),a%=base,base/=10;
putchar('\n');
}
int main()
{
int k;
read(n),read(k);
int i;
base=1;
while(base<=k)base<<=1;
int last=1;
for(i=1;i<=n;i++)
read(Line[i].x),read(Line[i].y),read(Line[i].z),Line[i].ans=0,Line[i].del=0,Line[i].time=1;
sort(Line+1,Line+1+n);
for(i=2;i<=n;i++)
if(Line[i].x==Line[last].x&&Line[i].y==Line[last].y&&Line[i].z==Line[last].z)
Line[last].time++,Line[i].del=true;
else last=i;
int con=0;
for(i=1;i<=n;i++)
if(!Line[i].del) Swap[++con]=Line[i];
for(i=1;i<=con;i++)
Line[i]=Swap[i];
Div(1,con);
for(i=1;i<=con;i++)
level[Line[i].ans+Line[i].time-1]+=Line[i].time;
for(i=1;i<=n;i++)
print(level[i-1]);
return 0;
}