奇怪的双端队列
题目描述
给你一个大小为 N 的双端队列 Q,和一个大小为 M 的查询数组 A。
对于每个查询 A[i] = [idx, val],你要把 Q 里从队头开始数的第 idx 个元素增加 val,然后把 Q 内的所有元素复制到一个新的双端队列 Q2, 保持 Q 内的元素不变, 在这之后你可以对 Q2 执行以下两种操作任意次:
把队头的元素移到队尾,减少 C1 分。
把队尾的元素移到队头,减少 C2 分。
在上面两种操作执行任意次之后,上面两种操作不能再被执行。此时可以执行以下任意两种操作最多 K 次:
把队头的元素 V 弹出,获得 V 分。
把队尾的元素 V 弹出,获得 V 分。
请你对每个查询, 分别输出操作后的最大分数。
输入描述
第一行有三个正整数 N, M, K,分别代表队列的大小 和 查询的数量 和后两种操作的最大执行次数。
第二行有两个整数 C1, C2,分别代表执行第一种操作减少的分数 和 执行第二种操作减少的分数。
第三行有 N 个整数,第 i 个整数代表队列里从队头开始数的第 i 个元素。
然后有 M 行,每一行有两个整数 idx, val, 代表查询的值。
输出描述
输出有 M 行,每一行有一个整数,代表操作后最大的分数。
输入示例
3 2 1
1 1
1 1 1
1 1
2 100
提示信息
1 <= N, M <= 100000
1 <= K < N
1 <= C1, C2 <= 1000000000
1 <= Q[i] <= 1000000000
1 <= idx <= N
1 <= val <= 1000000000