当前位置：网站首页>bzoj3262 Flowers bloom on Mo

bzoj3262 Flowers bloom on Mo

2022-08-08 15:14:00 【51CTO】

http://www.elijahqi.win/2018/03/08/bzoj3262/ ‎
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
splay+树状数组 for the first dimension 排序 for the second dimension Make a tree-like array For the third dimension in eachsplaymaintain something 每次log^2查询即可 Watch out for repetition Pack them up

       
       #include<cstdio>
       
#include<algorithm>
       
#define N 110000
       
#define M 220000 
       
using namespace std;
       
inline char gc(){
       
    static char now[1<<16],*S,*T;
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
    return *S++;
       
}
       
inline int read(){
       
    int x=0,f=1;char ch=gc();
       
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
       
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
       
    return x*f;
       
}
       
struct node{
       
    int a,b,c;
       
}qr[N];
       
int size[20*N],cnt[20*N],v[20*N],fa[20*N],c[20*N][2],rt[N<<1],ans[N],mx,n,num;
       
inline bool cmp(const node &a,const node &b){
       
    return a.a==b.a?(a.b==b.b?a.c<b.c:a.b<b.b):a.a<b.a;
       
}
       
inline void update(int x){
       
    size[x]=size[c[x][0]]+cnt[x]+size[c[x][1]];
       
}
       
inline void rotate(int x,int &tar){
       
    int y=fa[x],z=fa[y];
       
    if (y==tar) tar=x;else c[z][c[z][1]==y]=x;
       
    int l=c[y][1]==x,r=l^1;
       
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
       
    c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
       
}
       
inline void splay(int x,int &tar){
       
    while(x!=tar){
       
        int y=fa[x],z=fa[y];
       
        if (y!=tar){
       
            if (c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar);
       
        }rotate(x,tar);
       
    }
       
}
       
inline void insert1(int &x,int vv,int f,int id){
       
    if (!x) {x=++num;size[x]=cnt[x]=1;v[x]=vv;fa[x]=f;splay(x,rt[id]);return;}
       
    if (v[x]==vv){++cnt[x],++size[x];splay(x,rt[id]);return;}
       
    if (vv<v[x]) insert1(c[x][0],vv,x,id);else insert1(c[x][1],vv,x,id);
       
}
       
inline void add(int b,int c){
       
    for (int i=b;i<=mx;i+=i&(-i)) insert1(rt[i],c,rt[i],i);
       
}
       
inline int qr1(int x,int vv){
       
    if (!x) return 0;
       
    if (vv<v[x]) return qr1(c[x][0],vv);
       
    if (vv==v[x]) return size[c[x][0]]+cnt[x];
       
    return size[c[x][0]]+cnt[x]+qr1(c[x][1],vv);
       
}
       
inline int query(int b,int c){
       
    int sum=0;for (int i=b;i;i-=i&(-i)) sum+=qr1(rt[i],c);
       
    return sum;
       
}
       
inline void print(int x){
       
    if (c[x][0]) print(c[x][0]);
       
    printf("%d %d,cnt[x],v[x]);
       
    if (c[x][1]) print(c[x][1]);
       
}
       
int main(){
       
    freopen("bzoj3262.in","r",stdin);
       
    n=read();mx=read();for (int i=1;i<=n;++i) qr[i].a=read(),
       
    qr[i].b=read(),qr[i].c=read();sort(qr+1,qr+n+1,cmp);int tmp=0;
       
    for (int i=1;i<=n;++i){
       
        if (qr[i].a==qr[i+1].a&&qr[i].b==qr[i+1].b&&qr[i].c==qr[i+1].c) ++tmp;
       
        else ans[query(qr[i].b,qr[i].c)]+=tmp+1,tmp=0;add(qr[i].b,qr[i].c);
       
    }
       
    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.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.

cdq分治 Pay attention to packaging and sorting details

       
       #include<cstdio>
       
#include<algorithm>
       
#define N 110000
       
#define M 220000 
       
using namespace std;
       
inline char gc(){
       
    static char now[1<<16],*S,*T;
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
    return *S++;
       
}
       
inline int read(){
       
    int x=0,f=1;char ch=gc();
       
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
       
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
       
    return x*f;
       
}
       
struct node{
       
    int a,b,c,nm,ans;
       
}qr[N],tmp[N],qr1[N];
       
int s[M],ans[N],mx,n;
       
inline bool cmp(const node &a,const node &b){
       
    return a.a==b.a?(a.b==b.b?a.c<b.c:a.b<b.b):a.a<b.a;
       
}
       
inline void add(int x,int v){for (;x<=mx;x+=x&(-x)) s[x]+=v;}
       
inline int query(int x){
       
    int tmp=0;while(x) tmp+=s[x],x-=x&(-x);return tmp;
       
}
       
inline void clear(int x){
       
    for (;x<=mx;x+=x&(-x)) if (!s[x]) return;else s[x]=0;
       
}
       
inline void cdq(int l,int r){
       
    if (l==r) return;int mid=l+r>>1;
       
    cdq(l,mid);cdq(mid+1,r);int l1=l,l2=mid+1,now=l;
       
    while(l1<=mid&&l2<=r){
       
        if (qr[l1].b<=qr[l2].b) add(qr[l1].c,qr[l1].nm),tmp[now++]=qr[l1++];
       
        else qr[l2].ans+=query(qr[l2].c),tmp[now++]=qr[l2++];
       
    }while(l1<=mid) tmp[now++]=qr[l1++];
       
    while(l2<=r) qr[l2].ans+=query(qr[l2].c),tmp[now++]=qr[l2++];
       
    for (int i=l;i<=mid;++i) clear(qr[i].c);
       
    for (int i=l;i<=r;++i) qr[i]=tmp[i];
       
}
       
int main(){
       
    freopen("bzoj3262.in","r",stdin);
       
    n=read();mx=read();for (int i=1;i<=n;++i) qr1[i].a=read(),
       
    qr1[i].b=read(),qr1[i].c=read();sort(qr1+1,qr1+n+1,cmp);int tot=0;
       
    for (int i=1;i<=n;++i){
       
        if (qr[tot].a==qr1[i].a&&qr[tot].b==qr1[i].b&&qr[tot].c==qr1[i].c)++qr[tot].nm;
       
        else qr[++tot]=qr1[i],qr[tot].nm=1;
       
    }cdq(1,tot);
       
    //for (int i=1;i<=tot;++i) printf("%d %d %d %d\n",qr[i].a,qr[i].b,qr[i].c,qr[i].ans);
       
    for (int i=1;i<=tot;++i) ans[qr[i].ans+qr[i].nm-1]+=qr[i].nm;
       
    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.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/220/202208081445530407.html

当前位置：网站首页>bzoj3262 Flowers bloom on Mo

bzoj3262 Flowers bloom on Mo

边栏推荐

猜你喜欢

随机推荐