标签：CDQ分治，树状数组
题目
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
分析
第一维按关键字排序并去重，记录相同的花有多少朵
然后CDQ分治，将l->mid和mid+1->r区间分别按照第二维的关键字排序
第三维以树状数组为下标，维护每一朵花的出现次数
每一次处理[l,mid]对smid+1,r]的影响时，只需考虑第二维的影响
当第二维符合要求时，将它的影响加入树状数组中
每查找完[mid+1,r]区间的一个操作，就更新答案
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
int tn,n,m,t[maxn<<1],ans[maxn];
struct node{int a,b,c,s,ans;}a[maxn],p[maxn];
inline bool cmp(node a,node b){
if(a.a==b.a&&a.b==b.b)return a.c<b.c;
return a.a==b.a?a.b<b.b:a.a<b.a;
}
inline bool operator < (node a,node b){return a.b==b.b?a.c<b.c:a.b<b.b;}
inline int lowbit(int x){return x&(-x);}
void modify(int x,int num){for(int i=x;i<=m;i+=lowbit(i))t[i]+=num;}
inline int query(int x){int re=0;for(int i=x;i;i-=lowbit(i))re+=t[i];return re;}
void solve(int l,int r){
if(l==r)return;int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
sort(p+l,p+mid+1);sort(p+mid+1,p+r+1);
int i=l,j=mid+1;
while(j<=r){
while(i<=mid&&p[i].b<=p[j].b){modify(p[i].c,p[i].s);i++;}
p[j].ans+=query(p[j].c);j++;
}
rep(j,l,i-1)modify(p[j].c,-p[j].s);
}
int main()
{
tn=read(),m=read();
rep(i,1,tn)a[i].a=read(),a[i].b=read(),a[i].c=read();
sort(a+1,a+1+tn,cmp);int cnt=0;
rep(i,1,tn){
cnt++;
if(a[i].a!=a[i+1].a||a[i].b!=a[i+1].b||a[i].c!=a[i+1].c){
p[++n]=a[i];
p[n].s=cnt;
cnt=0;
}
}
solve(1,n);
rep(i,1,n)ans[p[i].ans+p[i].s-1]+=p[i].s;
rep(i,0,tn-1)printf("%d\n",ans[i]);
return 0;
}
