HNOI2017 day1 T2 影魔
题目大意:
影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。
千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。
每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。
奈文摩尔有 n 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 1 到 n。第 i
个灵魂的战斗力为 k[i],灵魂们以点对的形式为影魔提供攻击力,对于灵魂对 i,j(i<j)来说,
若不存在 k[s](i<s<j)大于 k[i]或者 k[j],则会为影魔提供 p1 的攻击力(可理解为:当 j=i+1 时,
因为不存在满足 i<s<j 的 s,从而 k[s]不存在,这时提供 p1 的攻击力;当 j>i+1 时,若
max{k[s]|i<s<j}<=min{k[i],k[j]} , 则 提 供 p1 的 攻 击 力 ); 另 一 种 情 况 , 令 c 为
k[i+1],k[i+2],k[i+3]......k[j-1]的最大值,若 c 满足:k[i]<c<k[j],或者 k[j]<c<k[i],则会为影魔提
供 p2 的攻击力,当这样的 c 不存在时,自然不会提供这 p2 的攻击力;其他情况的点对,均不
会为影魔提供攻击力。
影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任意一段
区间[a,b],1<=a<b<=n,位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑 所有满足
a<=i<j<=b 的灵魂对 i,j 提供的攻击力之和。
顺带一提,灵魂的战斗力组成一个 1 到 n 的排列:k[1],k[2],...,k[n]。
题解:
设点对(i,j)的mx为max{k[s]|i<s<j},lpre[i]为i向左找第一个比i大的,rpre[i]向右找。
考虑对于每个i,以k[i]为mx的点对对答案的贡献。很明显,以k[i]为mx的点对(p,q)一定满足lpre[i]<=p<i,i<q<=rpre[i]。
把每个询问看成一个点(l,r)。i可以影响的询问是一个矩形,然后可以分成4个矩形分别加值就好了。
最新文章
- [1.1]Environment preset on a Windows server
- zabbix短信网关调用问题总结
- fuser 命令概述
- win7下 mysql主从配置实现
- codeforces Vasya and Digital Root
- Runloop与autoreleasePool联系
- Linq skip skipwhile take takewhile
- 深入理解viewport(转)
- CDN内容分发网络
- cssText的用法以及特点
- 直接用nose进行django项目测试并输出html报告
- maven打包 tomcat运行pom配置 或 打成jar包
- 201521123103 《Java学习笔记》 第七周学习总结
- mybatis源码学习--spring+mybatis注解方式为什么mybatis的dao接口不需要实现类
- 携程Apollo(阿波罗)配置中心在.NET Core项目快速集成
- SpringBoot实用小技巧之动态设置SpringBoot日志级别
- dubbo本地服务化实现(dubbo三)
- FB面经 Prepare: Count Unique Island
- RabbitMQ系列(三)RabbitMQ交换器Exchange介绍与实践
- day91-redis