题目
兔子们在玩k个串的游戏。首先,它们拿出了一个长度为n的数字序列,选出其中的一个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次)。
兔子们想知道,在这个数字序列所有连续的子串中,按照以上方式统计其所有数字之和,第k大的和是多少。
题解
首先最简单的一个暴力想法就是枚举每个左端点,再枚举每个右端点,然后计算和并取最大值$O(n^3)$
但这样其实会有大量的重复计算,改进算法就是要尽量去除重复的计算。
考虑优化转移的过程,第一次的扫描(以1为左端点)肯定是无法避免的,我们要$arr[1~n]$保存结果
在计算以2为左端点的时候,观察下图,与第一次的区别就是少了一个1,但只要右端点跨过第二个1,后面的结果就跟第一次一样。
即,对于$l=2,r>=4$的区间,答案直接继承上一次的即可
否则就在原来的基础上减去1.
计算完之后,就把这一次的最大区间堆进一个堆里
之后的第三次,第四次...也是同理
我们可以用主席树来维护每次的结果数组,
即每次新建一个版本,对于要减的区间就进行区间修改,其他位置不变
另,为了节省空间,可以用永久标记,即不往下推,在更新最大值的时候相应地减去这个标记的值
在询问k的时候,每次把堆顶取出,设它是$[l~r]$这段区间
为了不让它再被选到,把l这棵树的第r个位置值设为-inf、
然后再在这颗树上再选一个最大的区间出来,塞进堆里。
反复k次,答案就出来了。
另外,为了知道最大区间的右端点,可以在主席树节点内追加一个pos,标记当前节点的最大值从何而来。
为了知道那一段区间要减去上一位的值,可以处理一个nxt[i]数组记录【第i位的值】下一次出现的位置
这个可以结合map $O(nlogn)$处理
代码
#include
#include
#include