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的每级花的数量。 Sample Input
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
Sample Output
3
1
3
0
1
0
1
0
0
1
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
题解 树套树，不会cdq，注意去重。
代码
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 15000005 int sum[N],add[N],ls[N],rs[N],sz,root[200005]; struct node{int s,c,m;}a[200005]; int ans[200005],num[200005]; bool cmp(node a,node b) { if (a.s!=b.s) return a.s<b.s; else if (a.c!=b.c) return a.c<b.c; else return a.m<b.m; } int n,k; using namespace std; inline int read() { int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } int lowbit(int x){return x&(-x);} void change(int &k,int l,int r,int x,int y) { if (!k) k=++sz; if (l==x&&r==y) { add[k]++; sum[k]+=r-l+1; return; } int mid=(l+r)>>1; if (y<=mid) change(ls[k],l,mid,x,y); else if (x>mid) change(rs[k],mid+1,r,x,y); else { change(ls[k],l,mid,x,mid); change(rs[k],mid+1,r,mid+1,y); } sum[k]=sum[ls[k]]+sum[rs[k]]+add[k]*(r-l+1); } int query(int &k,int l,int r,int x,int y) { if (!k) return 0; if (l==x&&r==y) return sum[k]; int mid=(l+r)>>1,ans=0; if (y<=mid) ans=query(ls[k],l,mid,x,y); else if (x>mid) ans=query(rs[k],mid+1,r,x,y); else ans=query(ls[k],l,mid,x,mid)+query(rs[k],mid+1,r,mid+1,y); return ans+add[k]*(y-x+1); } int main() { n=read();k=read(); for (int i=1;i<=n;i++) { a[i].s=read(); a[i].c=read(); a[i].m=read(); } sort(a+1,a+n+1,cmp); int p=1; for (int i=1;i<=n;i++) { if (a[i].s==a[i-1].s&&a[i].c==a[i-1].c&&a[i].m==a[i-1].m&&i!=1) { num[i]=num[i-1]+1;p++; for (int x=a[i].c;x<=k;x+=lowbit(x)) change(root[x],1,k,a[i].m,a[i].m); continue; } else if (i!=1) ans[num[i-1]]+=p,p=1; int sum=0; for (int x=a[i].c;x;x-=lowbit(x)) sum+=query(root[x],1,k,1,a[i].m); for (int x=a[i].c;x<=k;x+=lowbit(x)) change(root[x],1,k,a[i].m,a[i].m); num[i]=sum; } ans[num[n]]+=p; for (int i=0;i<n;i++) printf("%d\n",ans[i]); return 0; }