BZOJ3262: 陌上花开(三维偏序,CDQ分治)
2024-10-01 19:41:12
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
解题思路:
CDQ分治很好的模板。
运用了线段树/树状数组扫描线的思想。
或者说是离线解题时的控制端点动态更新。
动态处理问题获得解还是非常神的思路。
相当于将解集拆分成若干份,每份使用动态统计。
换句话说,就是将一定范围内的数据配对时间复杂度降低。
注意要撤销操作。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct pnt{
int x,y,z,f,w;
bool friend operator == (pnt a,pnt b)
{
return a.x==b.x&&a.y==b.y&&a.z==b.z;
}
bool friend operator != (pnt a,pnt b)
{
return !(a.x==b.x&&a.y==b.y&&a.z==b.z);
}
}p[],q[];
int n,k;
int cnt;
int d[];
int line[];
int has[];
int lowbit(int x)
{
return x&(-x);
}
bool cmx(pnt a,pnt b)
{
if(a.x==b.x&&a.y==b.y)
return a.z<b.z;
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
bool cmy(pnt a,pnt b)
{
if(a.x==b.x&&a.y==b.y)
return a.z<b.z;
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
void add(int p,int v)
{
while(p<=k)
{
line[p]+=v;
p+=lowbit(p);
}
return ;
}
int ask(int p)
{
int ans=;
while(p)
{
ans+=line[p];
p-=lowbit(p);
}
return ans;
}
void wrk(int l,int r)
{
int m=(l+r)>>;
sort(p+l,p+m+,cmy);
sort(p+m+,p+r+,cmy);
int tmp=-;
for(int i=l,j=m+;j<=r;j++)
{
for(;i<=m&&p[i].y<=p[j].y;i++)
{
add(p[i].z,p[i].w);
tmp=i;
}
p[j].f+=ask(p[j].z);
}
for(int i=l;i<=tmp;i++)
add(p[i].z,-p[i].w);
}
void cdq(int l,int r)
{
if(l==r)
return ;
int m=(l+r)>>;
cdq(l,m);
cdq(m+,r);
wrk(l,r);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
sort(q+,q+n+,cmx);
int wgt=;
for(int i=;i<=n;i++)
{
wgt++;
if(q[i]!=q[i+])
{
p[++cnt]=q[i];
p[cnt].w=wgt;
wgt=;
}
}
swap(cnt,n);
cdq(,n);
for(int i=;i<=n;i++)
has[p[i].f+p[i].w-]+=p[i].w;
for(int i=;i<cnt;i++)
printf("%d\n",has[i]);
return ;
}
最新文章
- php apache用户写文件夹权限设置
- Android最佳实践之UI篇
- AngularJS-MVC
- PHP Document 注释标记及规范 &;&; PHP命名规范
- QTabWiget Change Color 改变颜色
- Angular数据双向绑定
- Android笔记:百度地图与高德地图坐标转换问题
- x9015数字电位器应用
- jdbc(1)(一)
- Linux 文件权限于目录配置
- __x__(23)0907第四天__浏览器默认样式
- 为什么HashMap初始大小为16,为什么加载因子大小为0.75,这两个值的选取有什么特点?
- 利用 yEd 软件做元数据管理
- go语言,golang学习笔记1 官网下载安装,中文社区,开发工具LiteIDE
- 打印函数 lodop
- mysql limit 优化
- 二叉树—-1(No.9HN省赛小题)
- jvm高级特性(1)(内存泄漏实例)
- 如何解决abd.exe已停止工作
- 网站UI分析
热门文章
- Unity UGUI——UI基础,Canvas
- Android程序猿自己动手制作.9.png图片
- .net framework tools
- netsh http的使用
- 24.桌面移动qq
- HDU 4372 Count the Buildings 组合数学
- 消息推送学习一、原生Socket的使用
- codeforces 701 B. Cells Not Under Attack
- 判断控件的CGRect是否重合,获取控件的最大XY值
- 处理SpringMVC的时间错误:Field error in object &#39;sysDatumedetai&#39; on field &#39;storagetime&#39;: rejected value [2017-11-27];