Vases and Flowers HDU - 4614 线段树 + 二分
发布日期:2021-09-25 23:58:03 浏览次数:11 分类:技术文章

本文共 2326 字,大约阅读时间需要 7 分钟。

题意:编号为 0 ~ n - 1 个花瓶,有两个操作
(1)以 a 为起点,选择之后的 k 个花瓶放上花,输出左右端点。
(2)清空 l ~ r 的所有花瓶中的花,输出清除的花数量
对于第二个操作就是线段树区间赋值和区间查询了。
第一个操作如果知道左右端点直接区间赋值即可。现在问题是怎么求左右端点。比较显然可以在线段树上进行二分,分别二分出来第一个数位置和最后一个数位置。如果填不满k个的话显然第二个答案是INF,不会被更新。那么就需要把k改成 l ~ n - 1 中空花瓶个数,再二分一次就行了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;struct Node{ int l,r; int sum,lazy;}tr[N<<2];void pushup(int u){ tr[u].sum=tr[L].sum+tr[R].sum;}void pushdown(int u){ if(tr[u].lazy==-1) return; tr[L].lazy=tr[R].lazy=tr[u].lazy; tr[L].sum=Len(L)*tr[u].lazy; tr[R].sum=Len(R)*tr[u].lazy; tr[u].lazy=-1;}void build(int u,int l,int r){ tr[u]={ l,r,0,-1}; if(l==r) { tr[u].sum=1; return; } build(L,l,Mid),build(R,Mid+1,r); pushup(u);}void modify(int u,int l,int r,int c){ if(tr[u].l>=l&&tr[u].r<=r) { tr[u].sum=Len(u)*c; tr[u].lazy=c; return; } pushdown(u); if(l<=Mid) modify(L,l,r,c); if(r>Mid) modify(R,l,r,c); pushup(u);}int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; pushdown(u); int ans=0; if(l<=Mid) ans+=query(L,l,r); if(r>Mid) ans+=query(R,l,r); return ans;}void solve(int LL,int C){ int l=LL,r=n-1,ans1=INF,ans2=INF; while(l<=r) { int mid=l+r>>1; if(query(1,l,mid)>=1) r=mid-1,ans1=mid; else l=mid+1; } l=LL,r=n-1; while(l<=r) { int mid=l+r>>1; int c=query(1,l,mid); if(c>=C) r=mid-1,ans2=mid; else C-=c,l=mid+1; } if(ans1==INF&&ans2==INF) puts("Can not put any one."); else { if(ans2==INF) { C=query(1,LL,n-1); l=LL,r=n-1; while(l<=r) { int mid=l+r>>1; int c=query(1,l,mid); if(c>=C) r=mid-1,ans2=mid; else C-=c,l=mid+1; } } printf("%d %d\n",ans1,ans2); modify(1,ans1,ans2,0); }}//0 1 2 3 4 5 6 7 8 9//0 0 1 1 1 1 0 0 0 0int main(){ // ios::sync_with_stdio(false);// cin.tie(0); int _; scanf("%d",&_); int T=0; while(_--) { scanf("%d%d",&n,&m); build(1,0,n-1); while(m--) { int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==1) solve(l,r); else { printf("%d\n",r-l+1-query(1,l,r)); modify(1,l,r,1); } } puts(""); } return 0;}/**/

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/108302895 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Educational Codeforces Round 36 (Rated for Div. 2) E 线段树 || 珂朵莉树
下一篇:CodeForces - 896C 珂朵莉树

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月05日 23时45分32秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历 2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具 2019-04-21
英特尔cpu发布时间表_被嘲讽的英特尔核显,强大能力其实超乎你的想象 2019-04-21
chi2inv函数 matlab_MATLAB概率和统计(2) 2019-04-21
lisp修改上一个图素_在Windows上安装Haskell 2019-04-21
ad19 导出step 没有pcb_几款主流PCB软件哪个最好用,你用过几款? 2019-04-21
json mysql 字段 默认值_Newtonsoft.Json 六个超简单又实用的特性,值得一试 【上篇】... 2019-04-21
ocdma相干非相干_《Acconeer 60GHz脉冲相干雷达芯片:A111》 2019-04-21
修改表格字体颜色_Excel技巧:Excel如何修改字体颜色 2019-04-21
native react 变颜色 点击_React Native主动更改StackNavigator标头颜色 2019-04-21
prism项目搭建 wpf_WPF MVVM使用prism4.1搭建 2019-04-21
python发微信红包群_用Python实现微信自动化抢红包,再也不用担心抢不到红包了... 2019-04-21
python中func自定义函数_Python函数之自定义函数&作用域&闭包 2019-04-21
wget连接指定端口_端口通不通 telnet wget ssh 2019-04-21
eureka 调用服务_Spring Cloud微服务架构从入门到会用(二)—服务注册中心Eureka... 2019-04-21
easyexcel 工具类_问了个在阿里的同学,他们常用的15款开发者工具! 2019-04-21
mysql统计结果大于0时返回true_mysql表查询练习 2019-04-21