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
Source
传送门
先用树套树写一遍……
三维偏序问题，首先其实就是按照第一维排序，然后就可以只看2，3两维了；
对于这样的情况……就用树套树吧……
用树状数组维护第二维，然后用平衡树维护第三维。。
树状数组和平衡树如何求得排名？。。不多说了吧。
注意不可以啥啥树状数组套树状数组哦……
树状数组怎么动态开点= =
啊对了对了一定要注意花的属性完全相同的情况……
如何处理看我主程序吧。。
好吧水题水题……
不过这个写好常数是真的大……
改天用cdq分治写一发。。虽然都是两个log级别，，但是后者常数<<树套树呀……
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;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
M=100005,
KK=200005,
N=4000005;
int n,K,tot;
int Ans[M],root[KK];
struct flower{
int s,c,m;
}flo[M];
struct Splay{
int pre,son[2],sz,occ,num;
}tree[N];
bool cmp(flower x,flower y){
if (x.s==y.s)
if (x.c==y.c) return x.m<y.m;
else return x.c<y.c;
else return x.s<y.s;
}
int lowbit(int x){
return x&(-x);
}
void up(int id){
tree[id].sz=tree[tree[id].son[0]].sz+tree[tree[id].son[1]].sz+tree[id].occ;
}
void newnode(int id,int x){
tree[id].num=x;
tree[id].occ=tree[id].sz=1;
tree[id].pre=tree[id].son[0]=tree[id].son[1]=0;
}
void Rotate(int x){
int y=tree[x].pre,z=tree[y].pre,l,r;
if (tree[y].son[0]==x) l=0; else l=1;
r=l^1;
if (z)
if (tree[z].son[0]==y) tree[z].son[0]=x;
else tree[z].son[1]=x;
tree[x].pre=z; tree[y].pre=x;
tree[y].son[l]=tree[x].son[r];
tree[tree[x].son[r]].pre=y;
tree[x].son[r]=y;
up(y);
}
void splay(int rt,int x,int goal){
while (tree[x].pre!=goal){
int y=tree[x].pre,z=tree[y].pre;
if (z!=goal)
if (tree[z].son[0]==y^tree[y].son[0]==x) Rotate(x);
else Rotate(y);
Rotate(x);
}
up(x);
if (!goal) root[rt]=x;
}
void insert(int rt,int id,int x){
int u=root[rt],v;
while (u){
v=u;
if (tree[u].num==x){
tree[u].occ++,tree[u].sz++;
splay(rt,u,0);
return;
}
if (tree[u].num>x) u=tree[u].son[0];
else u=tree[u].son[1];
}
newnode(id,x);
if (!root[rt]) root[rt]=id;
else{
tree[id].pre=v;
if (tree[v].num>x) tree[v].son[0]=id;
else tree[v].son[1]=id;
}
splay(rt,id,0);
}
int findminer(int rt,int x){
int u=root[rt],t=0;
while (u)
if (tree[u].num<=x){
t+=tree[tree[u].son[0]].sz+tree[u].occ;
if (tree[u].num==x) return t;
u=tree[u].son[1];
} else u=tree[u].son[0];
return t;
}
void update(int x,int num){
for (int i=x;i<=K;i+=lowbit(i))
insert(i,++tot,num);
}
int query(int x,int num){
int t=0;
for (int i=x;i;i-=lowbit(i))
t+=findminer(i,num);
return t;
}
int main(){
tot=0;
memset(Ans,0,sizeof(Ans));
n=read(),K=read();
for (int i=1;i<=n;i++)
flo[i].s=read(),flo[i].c=read(),flo[i].m=read();
sort(flo+1,flo+1+n,cmp);
int len=1;
for (int i=1;i<=n;i++)
if (flo[i+1].s==flo[i].s && flo[i+1].c==flo[i].c
&& flo[i+1].m==flo[i].m){
update(flo[i].c,flo[i].m);
len++;
continue;
} else{
Ans[query(flo[i].c,flo[i].m)]+=len;
update(flo[i].c,flo[i].m);
len=1;
}
for (int i=0;i<n;i++)
printf("%d\n",Ans[i]);
return 0;
}
