#P17874. All the Trades Are the Best

All the Trades Are the Best

题目描述

某只股票的价格每天重复相同的规律。一天分为 nn 个等长时段,第 ii 个时段的价格为 aia_i。第 nn 个时段结束后,紧接着是次日的第 11 个时段。

给定 qq 个工作时间段。第 ii 个时间段从 lil_i 开始,到 rir_i 结束,两端均包含:

  • 若 li≤ril_i\le r_i,时段顺序为 li,li+1,…,ril_i,l_i+1,\ldots,r_i;
  • 若 li>ril_i>r_i,时段顺序为 li,li+1,…,n,1,…,ril_i,l_i+1,\ldots,n,1,\ldots,r_i。

每个工作时间段内最多完成 kk 次交易。每次交易先买入一股,再在严格更晚的时段卖出,收益为卖出价格减买入价格。任何时候最多持有一股股票,卖出后才能再次买入。全部买卖必须在当前工作时间段内完成。

也可以不交易,此时收益为 00。对每个工作时间段,独立求出最大总收益。

输入格式

第一行包含三个整数 n,k,qn,k,q。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

接下来 qq 行,每行包含两个整数 li,ril_i,r_i。

输出格式

输出 qq 行,第 ii 行为第 ii 个工作时间段的最大总收益。

样例

6 2 3
3 1 4 1 5 9
2 5
5 2
4 4
7
4
0

数据范围与特殊保证

  • 1≤n≤1051\le n\le10^5,1≤k≤8001\le k\le800,1≤q≤3×1051\le q\le3\times10^5;
  • 1≤ai≤1061\le a_i\le10^6,1≤li,ri≤n1\le l_i,r_i\le n。

记当前工作时间段的时段数为 leni\mathrm{len}_i。若 li≤ril_i\le r_i,则 leni=ri−li+1\mathrm{len}_i=r_i-l_i+1;否则 leni=n−li+1+ri\mathrm{len}_i=n-l_i+1+r_i。

每个询问的 lil_i 和 leni\mathrm{len}_i 分别从 [1,n][1,n] 和 $[\max(1,\lfloor0.15n\rfloor),\max(1,\lfloor0.85n\rfloor)]$ 独立均匀随机生成,rir_i 由它们唯一确定。 n=1n=1 时总是得到 (1,1)(1,1)。