#P10385. [2021年联测]不会吧不会吧不会真的有人没有AK吧

    ID: 9503 传统题 6000ms 128MiB 尝试: 10 已通过: 1 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS数据结构普通线段树动态规划线性 DP数值计算与优化凸性/单峰性判定多项式与生成函数卷积转化排序与序列处理双指针合并有序序列WQS 二分离线与分治并行二分查询排序CF3100

[2021年联测]不会吧不会吧不会真的有人没有AK吧

不会吧不会吧不会真的有人没有 AK 吧 (rated)

【问题描述】

2031 年。短短十年,世界被推向了崩溃的边缘。海平面上升不断、经济崩溃、联盟破裂,新闻头条接连不断。2033 年 10 月 9 日。“齐塔(Zeta)飓风。世界首场 6 级风暴。”2034 年 1 月 11 日。“全球食物、燃料短缺引发第二次大萧条。”2035 年 8 月 8 日。“德国崩溃后,欧盟正式解体。”

遭受遗弃的流离失所者们组成了涣散舰队寻找避风港。他们中有的出生普通家庭、有的是农民、医生、工程师,还有士兵......有的人曾经身享特权,有的人曾经贫苦挣扎,出身背景天壤地别的他们如今被迫走到一起,决心为生存奋战。媒体称他们为“无属邦者”。而他们自称为......“无邦者”。

2037 年。人类适应了世界的新常态。能源、沙漠灌溉、水力堤坝和海堤等方面的革新拯救了沿海城市,开垦了农田并重建了补给链。抱着能够走向稳定的希望,一些国家重新打开了边界。然而,由于无法将 12 亿人全部遣返,无邦者们成为了所有的经济、军队和社会政策制定中永久的一部分。许多无邦者仍然不信任流放自己的政府并拒绝重新回国。无邦者的领导者们初露头角并启发了一种不受前国籍束缚的新身份,在旧世界和新常态之间划清了界线。我们是无邦者成为了集结的呐喊。在世界重建的同时,为了在这个正在快速变化的世界中争夺控制权,最后的两个超级大国——美国和俄罗斯之间燃起了摩擦的火花。

2040 年。一场突如其来的太空残骸风暴产生了“凯斯勒效应”,导致超过 70% 的轨道卫星发生故障并坠落地球。原因不明。后续的断电造成了大规模的破坏。飞机纷纷坠毁。通讯网接连崩溃。本已堵塞的全球补给链陷入停滞。石油、粮食、煤炭的价格直线飙升。据未经证实的说法有 10 万人丧生。世界濒临崩溃。没有互联网。没有导航。没有监控。没有风暴预警。一夜之间,各地政权之间的信任灰飞烟灭。没人能互相监视,所以也没人能够互相相信。俄美两国都认为对方导致了大断电,还有一些人则怀疑无邦者是这一切的幕后黑手,指责他们试图散布无政府主义。 无邦者中的前军人们和训练有素的战斗专家们挺身而出并组建了武装特遣队,以在不断紧张的局势中保护自己。

食物和燃料的短缺引发了一场美俄之间的秘密战争。双方为了规避责任均派遣了无邦者特遣队在不断升级的资源冲突中为各自争取利益——并许诺把残羹剩饭分给这些难民。2042 年。全面战争一触即发。无邦者们除了选边站队别无选择,他们不为旗帜而战,而是为自己的未来而战。他们的战争就是你的故事。

虽然战地 2042 有巨大多 bug 以及不平衡性,但这并不影响你做题。

现在有一个数列A,∣A∣=nA,|A|=n,你需要求出如果恰好选kk个连续子段,它们的和最大为多少。

可是现在都已经 2202 年了,这个问题已经是 well-known 的了,相信大家都有 114514 种不同的解法。

为了让这场比赛更加有趣,于是你给出题人出了你的威力加强版:现在有qq组询问。在每组询问中你需要对于 [li,ri][l_{i},r_{i}] 的区间求出如果恰好选 kik_i 个两两没有公共位置的非空连续子段(允许相邻),它们的和最大为多少。

询问保证 1≤li≤ri≤n1\le l_i\le r_i\le n、0≤ki≤ri−li+10\le k_i\le r_i-l_i+1;ki=0k_i=0 时不选任何子段,答案为 00。子段均位于给定区间内。

但是出题人发现自己并不会做,认为这个问题不可做,要求你拿出一个解法。 如果你给出了这个问题的做法,出题人就会给你一个小礼物——战地 2042 的十折优惠券 (0% off)。

【输入格式】

第一行两个数n,qn,q,分别表示数列大小以及询问次数。

接下来一行nn个数,表示AA。

接下来qq行,每行三个数li,ri,kil_{i},r_{i},k_{i}表示询问。

【输出格式】

qq行,每行一个数表示答案。

【样例 1 输入】

6 5
-1 1 -4 5 -1 4
2 3 1
4 4 1
2 6 4
3 4 2
2 5 1

【样例输出】

1
5
9
1
5

【样例解释】

NIE

【数据范围】

若 n=0n=0,则必须有 q=0q=0,此时输出为空。

对于所有数据保证 0≤n,q≤50000,∣ai∣≤100000\le n,q\le 50000,|a_{i}|\le 10000。

子任务编号 特殊性质 分数 依赖
0 q≤1q\le 1 0 无
1 n,q≤1000n,q\le 1000 20
2 q≤20q\le 20
3 n,q≤10000n,q\le 10000 2
4 无 40 3