C++之路进阶——bzoj3262(陌上花开)
2024-08-25 06:30:34
F.A.Qs | Home | Discuss | ProblemSet | Status | Ranklist | Contest | ModifyUser gryz2016 | Logout | 捐赠本站 |
---|
Notice:由于本OJ建立在Linux平台下,而许多题的数据在Windows下制作,请注意输入、输出语句及数据类型及范围,避免无谓的RE出现。
3262: 陌上花开
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 812 Solved: 361
[Submit][Status][Discuss]
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
题解:
三维片续集,将a排序,用树状数组插入b,再在树状数组中建立treap,维护c。
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define M 5000005 using namespace std; int n,m,tmp,sz,ans[],sum[],root[],s[M],ls[M],rs[M],rond[M],v[M],w[M]; struct ss
{
int a;
int b;
int c;
}a[M]; bool cmp (ss a,ss 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;
} int lowbit(int x) {return x&(-x);} void updata(int k) {s[k]=s[ls[k]]+s[rs[k]]+w[k];} int rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];updata(k);k=t;} int lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];updata(k);k=t;} void ins (int &k,int num)
{
if (!k) {k=++sz;rond[k]=rand();s[k]=w[k]=;v[k]=num;return;}
s[k]++;
if (num==v[k]) {w[k]++;return;}
else
if (num<v[k]) {ins(ls[k],num);if (rond[ls[k]]<rond[k]) rturn(k);}
else {ins(rs[k],num);if (rond[rs[k]]<rond[k])lturn(k);}
} void getrank(int k,int num)
{
if (!k) return;
if (num==v[k]) {tmp+=s[ls[k]]+w[k];return;}
num>=v[k]? tmp+=s[ls[k]]+w[k],getrank(rs[k],num):getrank(ls[k],num);
} void insert(int x,int num)
{
for (int i=x;i<=m;i+=lowbit(i))
ins(root[i],num);
} void ask(int x,int num)
{
for(int i=x;i;i-=lowbit(i))
getrank(root[i],num);
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
sort(a+,a+n+,cmp);
for (int i=;i<=n;i++)
{
if (a[i].a==a[i+].a&&a[i].b==a[i+].b&&a[i].c==a[i+].c&&i!=n)
sum[i+]=sum[i]+;
else
{
tmp=;
ask(a[i].b,a[i].c);
ans[tmp]+=sum[i]+;
}
insert(a[i].b,a[i].c);
}
for(int i=;i<n;i++)
printf("%d\n",ans[i]);
}
한국어 中文 فارسی English ไทย
版权所有 ©2008-2012 大视野在线测评 | 湘ICP备13009380号 | 站长统计
Based on opensource project hustoj.
最新文章
- 《CLR via C#》---枚举标志和标志位
- windows使用nginx实现网站负载均衡测试实例
- 判断scrollview是否滚动到了底部
- 查询Oracle中字段名带";.";的数据
- iOS10 UI教程管理层次结构
- HackerRank ";TBS Problem"; ~ NPC
- Linux下动态链接库 与gcc 选项
- Git教程(5)常用技巧之本地分支
- 使用Raphael 画图(一) 基本图形 (javascript)
- WiresShark 图解教程1
- Arch Linux 安装过程
- 1.2 Python开发环境
- ANSI 和 UNICODE 的函数对应表
- mysql No query specified
- IE外挂
- CF1119A Ilya and a Colorful Walk
- Centos 6.5 安装和使用docker
- CodeForce VKcup A
- dagScheduler
- 安装office2010提示要安装MSXML6.10.1129.0解决方法
热门文章
- NRF51822之pstorage介绍
- xftp的使用
- 15 款最好的 C/C++ 编译器和集成开发环境
- 【Android测试】【随笔】搜狗、腾讯技术交流会心得
- Asp.net Session保存到Redis: 使用 RedisSessionStateProvider
- 设计模式:迭代器模式(Iterator)
- mysql基本sql语句大全(基础用语篇)
- Linux 性能检测 - CentOS 安装 paramon
- No mapping found for HTTP request with URI [] in DispatcherServlet with name &#39;appServlet&#39;
- Android 开发之如何保证Service不被杀掉(broadcast+system/app)