记录编号	600223	评测结果	AAAA
题目名称	陌上花开	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	1.334 s
提交时间	2025-04-22 18:54:44	内存使用	16.73 MiB

#include<bits/stdc++.h>
using namespace std;
int T,n,m,op,xx,tp=1,tt,as,I=1e9,rt[1000005],ttt[1000005];
struct N{
	int l,r,v,p,sz,ct;
}a[2000005];
struct nm{
    int aa,bb,cc,id;
}abc[1000005];
void pd(int ps){
	a[ps].sz=a[a[ps].l].sz+a[a[ps].r].sz+a[ps].ct;return;
}
void zig(int &ps){
	int q=a[ps].l;
	a[ps].l=a[q].r,a[q].r=ps,ps=q;
	pd(a[ps].r),pd(ps);
}
void zag(int &ps){
	int q=a[ps].r;
	a[ps].r=a[q].l,a[q].l=ps,ps=q;
	pd(a[ps].l),pd(ps);
}
void ins(int &ps,int x){
    if(!ps){a[++tt]={0,0,x,rand(),1,1},ps=tt;return;}
	if(a[ps].v==x){a[ps].ct++,pd(ps);return;}
	if(x<a[ps].v){
		ins(a[ps].l,x);
		if(a[a[ps].l].p>a[ps].p) zig(ps);
	}
	if(x>a[ps].v){
		ins(a[ps].r,x);
		if(a[a[ps].r].p>a[ps].p) zag(ps);
		
	}
	pd(ps);
	return;
}
int vk(int ps,int x){
	if(!ps) return 0;	
	if(a[ps].v==x)  return a[a[ps].l].sz;
	if(a[ps].v>x) return vk(a[ps].l,x);
	if(a[ps].v<x) return vk(a[ps].r,x)+a[a[ps].l].sz+a[ps].ct;
}
bool cp(nm xx,nm yy){
    return xx.aa<yy.aa;
}
int sum(int xx,int yy){
    int ans=0;
    for(;xx;xx-=(xx&(-xx))) ans+=vk(rt[xx],yy+1)-1;
    return ans;
}
void add(int xx,int yy){
    for(;xx<=m;xx+=(xx&(-xx))) ins(rt[xx],yy);
    return;
}
int main(){
    freopen("FlowerOpen.in","r",stdin);
	freopen("FlowerOpen.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>abc[i].aa>>abc[i].bb>>abc[i].cc,abc[i].id=i;
    sort(abc+1,abc+n+1,cp);
    for(int i=1;i<=m;i++){
        rt[i]=++tt;
        a[tt]={0,0,-I,rand(),1,1};
	    ins(rt[i],I);
    }
    int i=1,ppp;
    while(i<=n){
        ppp=i;
        while(abc[i].aa==abc[i+1].aa) add(abc[i].bb,abc[i].cc),i++;
        add(abc[i].bb,abc[i].cc),i++;
        for(int j=ppp;j<i;j++) ttt[sum(abc[j].bb,abc[j].cc)-1]++;
    }
    for(int i=0;i<n;i++) cout<<ttt[i]<<"\n";
    return 0;
}