[bzoj3262]-陌上花开

题目（BZOJ）
题目（洛谷）
 
cdq裸题一道~
对s排序，对c分治，对m用树状数组维护，在分治时按c第一关键字，m第二关键字分别对[L,mid]&[mid+1,R]排个序进行处理，得到每个数的排名，
然后就做完了~

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=100050;
int n,k,ans[N],c[N<<1];
inline int lowbit(int x){return x&(-x);}
inline void change(int x,int v){while(x<=k){c[x]+=v;x+=lowbit(x);}}
inline int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
struct querys{
	int s,c,m,cnt,rank;
}q[N],b[N];
inline bool cmp1(const querys &x,const querys &y){
	if(x.s!=y.s)return x.s<y.s;
	if(x.c!=y.c)return x.c<y.c;
	return x.m<y.m;
}
inline bool cmp2(const querys &x,const querys &y){
	if(x.c!=y.c)return x.c<y.c;
	if(x.m!=y.m)return x.m<y.m;
	return x.s<y.s;
}
void solve(int L,int R){
	if(L==R){
		q[L].rank+=q[L].cnt-1;
		return;
	}
	int mid=(L+R)>>1,j=L;
	solve(L,mid);solve(mid+1,R);
	sort(q+L,q+mid+1,cmp2);
	sort(q+mid+1,q+R+1,cmp2);
	for(int i=mid+1;i<=R;++i){
		while(j<=mid&&q[j].c<=q[i].c){
			change(q[j].m,q[j].cnt);++j;
		}
		q[i].rank+=query(q[i].m);
	}
	for(int i=L;i<j;++i)change(q[i].m,-q[i].cnt);
}
int main(){
	int nn;
	read(nn),read(k);
	for(int i=1;i<=nn;++i){
		read(b[i].s),read(b[i].c),read(b[i].m);
		b[i].rank=1;
	}
	sort(b+1,b+nn+1,cmp1);
	for(int i=1;i<=nn;++i){
		if(i!=1&&b[i].s==b[i-1].s&&b[i].c==b[i-1].c&&b[i].m==b[i-1].m){
			q[n].cnt++;
		}
		else q[++n]=b[i],q[n].cnt=1;
	}
	sort(q+1,q+n+1,cmp1);
	solve(1,n);
	for(int i=1;i<=n;++i)ans[q[i].rank]+=q[i].cnt;
	for(int i=1;i<=nn;++i)printf(
	return 0;
}