当前位置：网站首页>bzoj3262 陌上花开

bzoj3262 陌上花开

2022-08-08 14:57: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+树状数组针对第一维排序针对第二维做一个树状数组针对第三维在每个splay上维护一些东西每次log^2查询即可注意重复的要把他们打包处理

       
       #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分治注意打包处理以及排序细节

       
       #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://blog.51cto.com/u_15744996/5555927

当前位置：网站首页>bzoj3262 陌上花开

bzoj3262 陌上花开

边栏推荐

猜你喜欢

随机推荐