[NOI2010]超级钢琴

题解：

题目并不难。

也就是找区间长度有限制的情况下的前k大值。

显然，每个端点都有可能作为区间的右端点。

以i为右端点的区间，左端点有一个范围:[i-R+1,i-L+1]

受BZOJ3689: 异或之

这个题的启发，我们先把每个端点作为右端点的最大值找出来。

然后放进堆里面。

取出一个，就把i作为右端点的第二大的放进堆里面即可。

怎么找这个第二大的呢？

法一：RMQ

发现，其实贡献是：sum[i]-sum[t],i-R+1<=t<=i-L+1

sum[i]是固定的。求得就是sum[t]的最小值，次小值、、、

对于上一次左端点t,下一次的左端点可能在t+1~i-L+1，或者：i-R+1~t-1

两者中取最小的sum[t]

不就是RMQ吗？

RMQ维护区间sum最小值即可。

法二：

区间最小值、次小值、。。第k小？

主席树！！！

直接查询第k小。简单粗暴。

[NOI2010]超级钢琴

原文：https://www.cnblogs.com/Miracevin/p/9858404.html