「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
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
1
3
0
1
0
1
0
0
1
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
题解
三维。。。第一维排序，第二维树状数组，第三维treap
cdq分治好像很优越啊有空去学。。。
|
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 76 77 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #define M 5000005 using namespace std; inline 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; } int n,m,sz,tmp; int root[200005],ans[100005],sum[100005]; int s[M],ls[M],rs[M],v[M],w[M],rnd[M]; struct data{int a,b,c;}a[100005]; inline bool cmp(data a,data b) { if(a.a==b.a&&a.b==b.b)return a.c<b.c; if(a.a==b.a)return a.b<b.b; return a.a<b.a; } inline int lowbit(int x){return x&(-x);} void update(int x) {s[x]=s[ls[x]]+s[rs[x]]+w[x];} void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;update(k);update(t);k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;update(k);update(t);k=t;} void ins(int &k,int num) { if(!k){k=++sz;rnd[k]=rand();v[k]=num;s[k]=w[k]=1;return;} s[k]++; if(num==v[k]){w[k]++;return;} else if(num<v[k]){ins(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);} else {ins(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);} } void getrank(int k,int num) { if(!k)return; if(num==v[k]){tmp+=s[ls[k]]+w[k];return;} else if(num<v[k])getrank(ls[k],num); else {tmp+=s[ls[k]]+w[k];getrank(rs[k],num);} } void ask(int x,int num) { for(int i=x;i;i-=lowbit(i)) getrank(root[i],num); } void insert(int x,int num) { for(int i=x;i<=m;i+=lowbit(i)) ins(root[i],num); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) a[i].a=read(),a[i].b=read(),a[i].c=read(); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { if(a[i].a==a[i+1].a&&a[i].b==a[i+1].b&&a[i].c==a[i+1].c&&i!=n) sum[i+1]+=sum[i]+1; else { tmp=0; ask(a[i].b,a[i].c); ans[tmp]+=sum[i]+1; } insert(a[i].b,a[i].c); } for(int i=0;i<n;i++) printf("%d\n",ans[i]); return 0; } |
理论上复杂度一样。。。但是cdq分治真心快啊
|
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 76 77 78 79 80 81 82 83 84 85 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,t[200005],ans[100005]; struct data{int a,b,c,s,ans;}a[100005],p[100005]; inline bool cmp(data a,data b) { if(a.a==b.a&&a.b==b.b)return a.c<b.c; if(a.a==b.a)return a.b<b.b; return a.a<b.a; } inline bool operator<(data a,data b) { if(a.b==b.b)return a.c<b.c; return a.b<b.b; } inline int lowbit(int x){return x&(-x);} inline void update(int x,int num) { for(int i=x;i<=m;i+=lowbit(i)) t[i]+=num; } inline int ask(int x) { int tmp=0; for(int i=x;i;i-=lowbit(i)) tmp+=t[i]; return tmp; } 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) { update(p[i].c,p[i].s); i++; } p[j].ans+=ask(p[j].c); j++; } for(int j=l;j<i;j++)update(p[j].c,-p[j].s); } int main() { int N=read();m=read(); for(int i=1;i<=N;i++) a[i].a=read(),a[i].b=read(),a[i].c=read(); sort(a+1,a+N+1,cmp); int cnt=0; for(int i=1;i<=N;i++) { 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); for(int i=1;i<=n;i++) ans[p[i].ans+p[i].s-1]+=p[i].s; for(int i=0;i<N;i++) printf("%d\n",ans[i]); return 0; } |
Subscribe
计数器 9786822
OI 课件=>
OI 课件=>