【洛谷】P4198 楼房重建(线段树)
2024-09-02 07:10:57
传送门
分析
被线段树按在地上摩擦 先把左边转化成斜率,那么这个题就转化成每次修改一个点的值,输出前缀最大值的个数
看到标签是线段树,所以还是想想线段树的做法吧
既然是线段树,那么就要将区间分成两半,那么左半区间可以直接递归下去做,右半区间就要考虑左半区间对它的影响
左半区间的最大值会对右半区间的前缀最大值的个数造成影响,所以询问时应该带上之前的最大值
考虑一次询问(l,r,x),表示l前面的数的最大值为x,区间(l,r)内的前缀最大值,那么每次就要输出询问(1,n,0)
用dp式子转移的思想对询问进行拆分
设mid=(l+r)/2,mx(l,r)表示l到r内的最大值
如果x>mx(l,mid),那么就左半区间就不可能存在前缀最大值,(l,r,x)的结果就等于(mid,r,x)
如果x<=mx(l,mid),那么询问(l,r,x)就可以拆成(l,mid,x)与(mid+1,r,mx(l,mid))。
注意到(mid+1,r,mx(l,mid))这个东西与x无关,可以在插入值的时候就处理它
所以对于每个询问(l,r,x)真正需要现场求的是(l,mid,x)或(mid,r,x),每次拆分区间长度减半,可以做到logn的复杂度
至于每次插入值修改(mid+1,r,mx(l,mid))时,也可以用同样的方法,总共有logn个区间,每个区间处理的复杂度为logn,所以为long^2n的复杂度
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,vr[maxn<<];double mx[maxn<<];
int que(int id,int l,int r,double L)
{
if(l==r)return mx[id]>L?:;
int mid=(l+r)>>;
if(L<=mx[id<<])return que(id<<,l,mid,L)+vr[id];
else return que(id<<|,mid+,r,L);
}
void fix(int id,int l,int r,int k,double v)
{
if(l==r){mx[id]=v;return;}
int mid=(l+r)>>;
k<=mid?fix(id<<,l,mid,k,v):fix(id<<|,mid+,r,k,v);
mx[id]=max(mx[id<<],mx[id<<|]);vr[id]=que(id<<|,mid+,r,mx[id<<]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,y;i<=m;i++)
scanf("%d%d",&x,&y),
fix(,,n,x,double(y)/double(x)),
printf("%d\n",que(,,n,));
}
最新文章
- java动态调用webservice
- *按类的某一字段排序(Lv)
- 2016HUAS暑假集训训练题 F - 简单计算器
- switch语句
- IE中无法执行JS脚本 解决WINDOWS SERVER 2008弹出INTERNET EXPLORER增强安全配置正在阻止来自下列网站的内容
- oracle系列--第一篇 数据库基础
- Scala中的Extractor
- 用QT创建新风格: QStyle
- Hibernate的BaseDao辅助类
- 流弊博客集锦(updating)
- Coursera 机器学习笔记(四)
- redis哨兵主从自动切换
- 将最小的OWIN身份验证添加到现有的ASP.NET MVC应用程序
- <;数据结构基础学习>;(四)链表 Part 2
- RHCE
- Python import语句导入模块语法[转]
- 优雅的使用列表推导式和lambda
- SQLite3命令操作大全
- react中多语言切换的实现方式
- JQuery中serialize()方法的使用
热门文章
- 使用JDK的zip编写打包工具类
- spring加载多个配置文件如何配置
- test aria2 on windows platform
- div中的“内容”水平垂直居中
- js utc转当地时间
- java服务端集成极光消息推送--详细开发步骤
- CentOS7源码安装Redis5.0.4非关系型数据库
- pyecharts绘制map地图
- https://www.runoob.com/linux/mysql-install-setup.html
- spring的@Scheduled定时任务,同一时间段的定时任务只会执行一个,其余的会被阻塞,@Scheduled注解定时任务并发执行解决办法,即多线程运行定时任务