BZOJ 3262: 陌上花开

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
HINT
题解

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
1
1
1

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

题解

我们来复习一下树套树！
多维的问题，其中一维永远可以用排序解决！然后第二维我们用树状数组，第三维用Treap！

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int Maxn=100010;
const int Maxk=200010;
int root[Maxk];
inline int lowbit(int x){
    return x&(-x);
}
struct Treap{
    int lx,rx;
    int num;
    int siz;
    int wei;
    int rnd;
};
Treap tree[Maxk*25];
int nume;
inline void update(int x){
    tree[x].siz=tree[tree[x].lx].siz+tree[tree[x].rx].siz+tree[x].wei;
}
inline void leftTurn(int &x){
    int y=tree[x].rx;
    tree[x].rx=tree[y].lx;
    tree[y].lx=x;
    tree[y].siz=tree[x].siz;
    update(x);
    x=y;
}
inline void rightTurn(int &x){
    int y=tree[x].lx;
    tree[x].lx=tree[y].rx;
    tree[y].rx=x;
    tree[y].siz=tree[x].siz;
    update(x);
    x=y;
}
void insert(int &x,int val,int nm){
    if (!x){
        x=++nume;
        tree[x].num=val;
        tree[x].wei=tree[x].siz=nm;
        tree[x].rnd=rand();
        return ;
    }
    tree[x].siz+=nm;
    if (tree[x].num==val) {
        tree[x].wei+=nm;
        return;
    }
    if (tree[x].num<val){
        insert(tree[x].rx,val,nm);
        if (tree[tree[x].rx].rnd<tree[x].rnd) leftTurn(x);
    }else{
        insert(tree[x].lx,val,nm);
        if (tree[tree[x].lx].rnd<tree[x].rnd) rightTurn(x);
    }
}
int query(int x,int val){
    if (!x) return 0;
    if (tree[x].num==val) return tree[tree[x].lx].siz+tree[x].wei;
    if (tree[x].num<val) return tree[tree[x].lx].siz+tree[x].wei+query(tree[x].rx,val);
    if (tree[x].num>val) return query(tree[x].lx,val);
}
inline void add(int b,int c,int nm){
    for (int i=b;i<=Maxk;i+=lowbit(i)) insert(root[i],c,nm);
}
inline int get(int b,int c){
    int ret=0;
    for (int i=b;i;i-=lowbit(i)) ret+=query(root[i],c);
    return ret;
}
int n,k;
struct Flower{
    int a,b,c;
    int index;
};
Flower f[Maxn+5];
int Ans[Maxk+5];
bool cmp(Flower a,Flower b){
    if (a.a!=b.a) return a.a<b.a;
    if (a.b!=b.b) return a.b<b.b;
    return a.c<b.c;
}
int sum[Maxn+5];
int main(){
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);
    for (int i=1;i<=n;i++) f[i].index=i;
    sort(f+1,f+n+1,cmp);
    for (int i=1;i<=n;i++) sum[i]=1;
    for (int i=1;i<=n;i++){
        if (f[i].a==f[i+1].a && f[i].b==f[i+1].b && f[i].c==f[i+1].c){
            sum[i+1]+=sum[i];
            continue;
        }
        add(f[i].b,f[i].c,sum[i]);
        Ans[get(f[i].b,f[i].c)-1]+=sum[i];
    }
    for (int i=0;i<n;i++) printf("%d\n",Ans[i]);
    return 0;
}

100

101

102

103

104

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int Maxn=100010;

const int Maxk=200010;

int root[Maxk];

inline int lowbit(int x){

return x&(-x);

}

struct Treap{

int lx,rx;

int num;

int siz;

int wei;

int rnd;

};

Treap tree[Maxk*25];

int nume;

inline void update(int x){

tree[x].siz=tree[tree[x].lx].siz+tree[tree[x].rx].siz+tree[x].wei;

}

inline void leftTurn(int &x){

int y=tree[x].rx;

tree[x].rx=tree[y].lx;

tree[y].lx=x;

tree[y].siz=tree[x].siz;

update(x);

x=y;

}

inline void rightTurn(int &x){

int y=tree[x].lx;

tree[x].lx=tree[y].rx;

tree[y].rx=x;

tree[y].siz=tree[x].siz;

update(x);

x=y;

}

void insert(int &x,int val,int nm){

if (!x){

x=++nume;

tree[x].num=val;

tree[x].wei=tree[x].siz=nm;

tree[x].rnd=rand();

return ;

}

tree[x].siz+=nm;

if (tree[x].num==val) {

tree[x].wei+=nm;

return;

}

if (tree[x].num<val){

insert(tree[x].rx,val,nm);

if (tree[tree[x].rx].rnd<tree[x].rnd) leftTurn(x);

}else{

insert(tree[x].lx,val,nm);

if (tree[tree[x].lx].rnd<tree[x].rnd) rightTurn(x);

}

int query(int x,int val){

if (!x) return 0;

if (tree[x].num==val) return tree[tree[x].lx].siz+tree[x].wei;

if (tree[x].num<val) return tree[tree[x].lx].siz+tree[x].wei+query(tree[x].rx,val);

if (tree[x].num>val) return query(tree[x].lx,val);

}

inline void add(int b,int c,int nm){

for (int i=b;i<=Maxk;i+=lowbit(i)) insert(root[i],c,nm);

}

inline int get(int b,int c){

int ret=0;

for (int i=b;i;i-=lowbit(i)) ret+=query(root[i],c);

return ret;

}

int n,k;

struct Flower{

int a,b,c;

int index;

};

Flower f[Maxn+5];

int Ans[Maxk+5];

bool cmp(Flower a,Flower b){

if (a.a!=b.a) return a.a<b.a;

if (a.b!=b.b) return a.b<b.b;

return a.c<b.c;

}

int sum[Maxn+5];

int main(){

scanf("%d%d",&n,&k);

for (int i=1;i<=n;i++)

scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);

for (int i=1;i<=n;i++) f[i].index=i;

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

for (int i=1;i<=n;i++) sum[i]=1;

for (int i=1;i<=n;i++){

if (f[i].a==f[i+1].a && f[i].b==f[i+1].b && f[i].c==f[i+1].c){

sum[i+1]+=sum[i];

continue;

}

add(f[i].b,f[i].c,sum[i]);

Ans[get(f[i].b,f[i].c)-1]+=sum[i];

}

for (int i=0;i<n;i++) printf("%d\n",Ans[i]);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑