hdu5861【线段树】
2024-09-06 09:23:04
题意:
有n个点,每个两两之间有一条路,给出每条路开放的花费,每条路只能打开关闭一次,然后m天里给出一个区间代表这条路必须在该天开放,求每天需要的花费。
思路:
这是一题纯粹用线段树搞的题。
我们可以看到:某第i个区间[s1,t1]的打开,如果存在第k(1<=k< i)个区间[s2,t2] (s2 >=s1 , t1>=t2),那么第k区间的所有路必须在[ k , i]时间段内打开。因为一旦关闭,之后那个就不行了,那么很明显是要求每条路的最早打开时间,最晚关闭时间了。
用两个vector把每条路(两两之间)的路的最早时间,最晚时间存起来。
那么之后的操作就是枚举每天,更新一下哪一条路在该天打开,哪一条路在该天关闭。这里的复杂度不大,因为最大n-1条路,每条路最多更新两次,那么复杂度应该是O((m+2nlog(n)))吧(不对请指出。。)然后更新完,此时根结点所存的权值就是这天的花费。
注意的就是:
线段树求区间最小最大时是大区间限制小区间。注意最底层的节点代表区间。
线段树好题啊;具体参考:点我
最新文章
- 出现个Expression(str != NULL)
- [转]Linux命令的返回值
- JavaScript 几种简单的table切换
- JQuery兼容IE6问题汇总(不断更新)
- 在windows上搭建ftp服务
- 2016 ACM/ICPC Asia Regional Shenyang Online 1009/HDU 5900 区间dp
- mysql定时脚本(event),类似oracle的job
- 【HDOJ】4162 Shape Number
- 配置SHH集群
- MongoDb C/java driver
- byte与sbyte的转换
- 8月9日,PS、计算机基础(预科)
- iOS pragma mark要使用
- Linux Set Command
- 近期学习的原生JS知识以及jQuery框架
- Vue 过滤器的使用
- [转]gitlab配置通过smtp发送邮件(QQ exmail腾讯企业为例)
- js数组元素,获得某个元素的最大值。
- websocket的属性readyState
- Vuejs——(9)组件——props数据传递