#P13622. Honorable Mention (open cup)

    ID: 12822 传统题 5000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100省选/NOI-WQS 二分普通线段树线性 DP凸性/单峰性判定双指针合并有序序列并行二分查询排序

Honorable Mention (open cup)

Ilya Zban 有一个数组 a1,a2,…,ana_1, a_2, \ldots, a_n 。数组的 [l…r][l \ldots r] 段是数组 al,al+1,…,ara_l, a_{l + 1}, \ldots, a_r 。 伊利亚有 qq 个有序三元组,其形式为 (l,r,k)(l, r, k) ,其中 1≤l≤r≤n1 \leq l \leq r \leq n 和 1≤k≤r−l+11 \leq k \leq r - l + 1 。

对于每个这样的三元组,他都要求你回答下面的问题:"线段 [l…r][l \ldots r] 的非空非相交子线段 kk 的元素之和的最大值是多少?

输入

第一行输入包含两个整数 nn 和 qq :数组中的元素个数和查询次数( 1≤n,q≤35 0001 \leq n, q \leq 35\,000 )。

第二行包含 nn 个空格分隔的整数 a1,a2,…,ana_1, a_2, \ldots, a_n :给定数组( −35 000≤ai≤35 000-35\,000 \leq a_i \leq 35\,000 )。

接下来的 qq 行包含查询。每一行都包含三个整数 ll 、 rr 、 kk :给定的线段以及在其上应该找到的不相交子线段的数量( 1≤l≤r≤n1 \leq l \leq r \leq n 、 1≤k≤r−l+11 \leq k \leq r-l+1 )。

输出

分行输出 qq 个整数:查询的答案。

5 5
-1 2 -3 4 -5
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5
4
6
5
2
-3
5 1
7 7 7 7 7
1 5 1
35

子任务划分

  • 子任务1:(10 分)— n ≤ 200, q ≤ 200。
  • 子任务2:(20 分)— n ≤ 5000, q ≤ 5000, k ≤ 3。
  • 子任务3:(15 分)— n ≤ 35000, q ≤ 200。
  • 子任务4:(20 分)— n ≤ 35000, q ≤ 35000, a_i ≥ 0。
  • 子任务5:(35 分)— n ≤ 35000, q ≤ 35000。