首页 > 代码库 > BZOJ3262: 陌上花开
BZOJ3262: 陌上花开
3262: 陌上花开
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 217 Solved: 104
[Submit][Status]
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
Source
树套树 CDQ分治
题解：
三维。。。第一维排序，第二维树状数组，第三维treap
具体实现就是每个树状数组的节点保存一颗treap，然后就可以查询了。
树套树就是强大！
刚开始为了节省时间把相同的节点同时加入，然后发现这样的rank就变小了T_T。。。
唉？貌似也可以搞？
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 200000+100014 #define maxm 400000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 struct rec{int x,y,z;}a[maxn];32 int n,m,tot,ls[maxm],rs[maxm],s[maxm],w[maxm],rnd[maxm],v[maxm],sum[maxn],ans[maxn],root[maxn];33 inline bool cmp(rec a,rec b)34 {35 return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.z<b.z);36 }37 inline void pushup(int k)38 {39 s[k]=s[ls[k]]+s[rs[k]]+w[k];40 }41 inline void rturn(int &k)42 {43 int t=ls[k];ls[k]=rs[t];rs[t]=k;pushup(k);pushup(t);k=t;44 }45 inline void lturn(int &k)46 {47 int t=rs[k];rs[k]=ls[t];ls[t]=k;pushup(k);pushup(t);k=t;48 }49 void ins(int &k,int x)50 {51 if(!k){k=++tot;s[k]=w[k]=1;ls[k]=rs[k]=0;rnd[k]=rand();v[k]=x;return;}52 s[k]++;53 if(x==v[k]){w[k]++;return;}54 else if(x<v[k]){ins(ls[k],x);if(rnd[ls[k]]>rnd[k])rturn(k);}55 else {ins(rs[k],x);if(rnd[rs[k]]>rnd[k])lturn(k);};56 }57 int rank(int k,int x)58 {59 if(!k)return 0;60 if(x==v[k])return s[ls[k]]+w[k];61 else if(x<v[k])return rank(ls[k],x);62 else return s[ls[k]]+w[k]+rank(rs[k],x);63 }64 inline void insert(int x,int y)65 {66 for(;x<=m;x+=x&(-x))ins(root[x],y);67 }68 inline int query(int x,int y)69 {70 int t=0;71 for(;x;x-=x&(-x))t+=rank(root[x],y);72 return t;73 }74 int main()75 {76 freopen("input.txt","r",stdin);77 freopen("output.txt","w",stdout);78 n=read();m=read();79 for1(i,n)a[i].x=read(),a[i].y=read(),a[i].z=read();80 sort(a+1,a+n+1,cmp);81 for1(i,n)sum[i]=1;82 for1(i,n)83 {84 if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)sum[i+1]+=sum[i];85 else ans[query(a[i].y,a[i].z)]+=sum[i];86 insert(a[i].y,a[i].z);87 } 88 for0(i,n-1)printf("%d\n",ans[i]);89 return 0; 90 }
我擦，一块加也行，那么rank就等于 query+sum[i]-1
结果加了这个优化才快了几百毫秒 T_T
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 200000+100014 #define maxm 400000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 struct rec{int x,y,z;}a[maxn];32 int n,m,tot,ls[maxm],rs[maxm],s[maxm],w[maxm],rnd[maxm],v[maxm],sum[maxn],ans[maxn],root[maxn];33 inline bool cmp(rec a,rec b)34 {35 return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.z<b.z);36 }37 inline void pushup(int k)38 {39 s[k]=s[ls[k]]+s[rs[k]]+w[k];40 }41 inline void rturn(int &k)42 {43 int t=ls[k];ls[k]=rs[t];rs[t]=k;pushup(k);pushup(t);k=t;44 }45 inline void lturn(int &k)46 {47 int t=rs[k];rs[k]=ls[t];ls[t]=k;pushup(k);pushup(t);k=t;48 }49 void ins(int &k,int x,int cnt)50 {51 if(!k){k=++tot;s[k]=w[k]=cnt;ls[k]=rs[k]=0;rnd[k]=rand();v[k]=x;return;}52 s[k]+=cnt;53 if(x==v[k]){w[k]+=cnt;return;}54 else if(x<v[k]){ins(ls[k],x,cnt);if(rnd[ls[k]]>rnd[k])rturn(k);}55 else {ins(rs[k],x,cnt);if(rnd[rs[k]]>rnd[k])lturn(k);};56 }57 int rank(int k,int x)58 {59 if(!k)return 0;60 if(x==v[k])return s[ls[k]]+w[k];61 else if(x<v[k])return rank(ls[k],x);62 else return s[ls[k]]+w[k]+rank(rs[k],x);63 }64 inline void insert(int x,int y,int cnt)65 {66 for(;x<=m;x+=x&(-x))ins(root[x],y,cnt);67 }68 inline int query(int x,int y)69 {70 int t=0;71 for(;x;x-=x&(-x))t+=rank(root[x],y);72 return t;73 }74 int main()75 {76 freopen("input.txt","r",stdin);77 freopen("output.txt","w",stdout);78 n=read();m=read();79 for1(i,n)a[i].x=read(),a[i].y=read(),a[i].z=read();80 sort(a+1,a+n+1,cmp);81 for1(i,n)sum[i]=1;82 for1(i,n)83 if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)sum[i+1]+=sum[i];84 else 85 {86 ans[query(a[i].y,a[i].z)+sum[i]-1]+=sum[i];87 insert(a[i].y,a[i].z,sum[i]);88 }89 for0(i,n-1)printf("%d\n",ans[i]);90 return 0; 91 }
BZOJ3262: 陌上花开
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。