【CJOJ2433】陌上花开 CDQ呲嘚秋分治

WA果然呲嘚秋分治跑得比树套树还快！！！（md理论复杂度不是一样的吗）

但树套树不知道比呲嘚秋高到哪里去辣装X用

Orz hzwer



第一维sort，第二维cdq归并，第三位BIT维护。。。

不要在意结构体名称

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

il int gi(){

    rg int x=0;rg bool flg=0;rg char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return flg?-x:x;

}

const int maxn=1e5+2,maxk=2e5+2;

struct frog{int knowledge,f,g,ans,tot;};

il bool operator ==(const frog&a,const frog&b){return a.knowledge==b.knowledge&&a.g==b.g&&a.f==b.f;}

il bool cmp(const frog&a,const frog&b){

	if(a.knowledge^b.knowledge)return a.knowledge<b.knowledge;

	if(a.f^b.f)return a.f<b.f;

	return a.g<b.g;

}

il bool mmp(const frog&a,const frog&b){

	if(a.tot==-1)return 0;if(b.tot==-1)return 1;

	return cmp(a,b);

}

frog f[maxn],tmp[maxn];

int n,k;

namespace bit{

	int t[maxk];

#define lb(o) ((o)&-(o))

	il vd add(int p,int num){while(p<=k)t[p]+=num,p+=lb(p);}

	il int sum(int p){static int ret;ret=0;while(p)ret+=t[p],p-=lb(p);return ret;}

#undef lb

}

namespace STO_CDQ_OTZ{

#define mid ((l+r)>>1)

	il vd merge(int __l,int __r,int l,int r,int L,int R){

		int tot=__l;

		while((l^L)&&(r^R))

			if(f[l].f<=f[r].f)bit::add(f[l].g,f[l].tot),tmp[tot++]=f[l++];

			else f[r].ans+=bit::sum(f[r].g),tmp[tot++]=f[r++];

		while(l^L)bit::add(f[l].g,f[l].tot),tmp[tot++]=f[l++];

		while(r^R)f[r].ans+=bit::sum(f[r].g),tmp[tot++]=f[r++];

		l=__l;while(l^L)bit::add(f[l].g,-f[l].tot),++l;

		rep(i,__l,__r)f[i]=tmp[i];

	}

	il vd cdq(int l,int r){

		if(l==r)return;

		cdq(l,mid),cdq(mid+1,r);

		merge(l,r,l,mid+1,mid+1,r+1);

	}

#undef mid

}

int ans[maxn];

int main(){

	n=gi(),k=gi();

	rep(i,1,n)f[i].knowledge=gi(),f[i].f=gi(),f[i].g=gi(),f[i].ans=0,f[i].tot=1;

	sort(f+1,f+n+1,cmp);

	int N=n,nnnn=n;

	rep(i,1,n)if(f[i]==f[i-1])f[i].tot=f[i-1].tot+1,f[i-1].tot=-1,--N;

	sort(f+1,f+n+1,mmp),n=N;

	STO_CDQ_OTZ::cdq(1,n);

	rep(i,1,n)ans[f[i].ans+f[i].tot-1]+=f[i].tot;

	rep(i,1,nnnn)printf("%d\n",ans[i-1]);

	return 0;

}