← 返回题目列表

AtCoder · joi2017ho_a

A. 焚风现象

中文机器翻译题面 查看原题

配点: 100 点

在IOI国家,风总是从海上吹向陆地。风是一个点 0 点 经过路线 1,地点 2,\ldots 时的点 吹直到 N 。点 JOI 的房子正在 N 建造。点 0 的海拔高度是 A_0 = 0 以及要点 i (1 \leqq i \leqq N) 的海拔高度是 A_i 。

风沿着地表吹,风的温度随着海拔的变化而变化。触及大海的点 0 处的风温为 0 度,以及所有 i (0 \leqq i \leqq N - 1),重点 i 点 经过路线 i + 1 期间风温的变化为 它仅取决于 A_i 和 A_{i + 1} ,如下所示。

  • A_i < A_{i + 1} 时,海拔高度为 1 随着风温升高, S 它下降了。
  • A_i \geqq A_{i + 1} 时,海拔高度为 1 随着风的温度降低, T 程度增加。

IOI国境内地壳运动活跃。你是Q 我们获得了每日地壳变形数据。j 日目 (1 \leqq j \leqq Q)中有L_j \leqq k \leqq R_j (1 \leqq L_j \leqq R_j \leqq N) 满足点的高程 由 A_k 是 X_j 更改。 当X_j 非负时,海拔高度为 这意味着它增加了 X_j , 当X_j 为负数时,海拔高度为 这意味着它将减少 |X_j| 。

你的工作是找出每次地壳变形发生后 JOI 家吹来的风的温度。

課題

给出地壳变形前的高程和地壳变形信息时,全部为整数 j (1 \leqq j \leqq Q),j 第一天发生地壳变形后的 JOI。编写一个程序来查找吹到你家的风的温度。


入力

从标准输入读取以下输入。 在

  • 1 行中, 4 整数 给出 N, Q, S, T 以空格作为分隔符。这些点都是JOI的家。 建于 N ,构造运动次数为 Q 海拔高度是 1 风的温度随着上升而升高。 S 程度降低,1 每次下降 T 代表程度的增加。
  • 继续 N + 1 行 i 行目 (1 \leqq i \leqq N + 1) 是重点 一个整数,表示 i - 1 处地壳变形前的高程 写入 A_{i - 1} 。
  • 继续 Q 行 j 行目 (1 \leqq j \leqq Q)中有3 整数 给出 L_j, R_j, X_j 以空格作为分隔符。这些是j 当日地壳变形点 海拔高度可达 L_j 到 R_j 代表 X_j 的更改。

出力

输出是 由 Q 行组成。标准输出 j 行目 (1 \leqq j \leqq Q)中有j 第一天发生地壳变形后的 JOI。输出吹到你家的风的温度。


制限

所有输入数据满足以下条件。

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq Q \leqq 200\,000.
  • 1 \leqq S \leqq 1\,000\,000.
  • 1 \leqq T \leqq 1\,000\,000.
  • A_0 = 0.
  • -1\,000\,000 \leqq A_i \leqq 1\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q).
  • -1\,000\,000 \leqq X_j \leqq 1\,000\,000 (1 \leqq j \leqq Q).

小課題

小課題 1 [30 点]

满足以下条件。

  • N \leqq 2\,000.
  • Q \leqq 2\,000.

小課題 2 [10 点]

  • S = T 得到满足。

小課題 3 [60 点]

  • 没有其他限制。

入力例 1

3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

出力例 1

-5
-7
-13
-13
-18

最初,地点 0, 1, 2, 3 的海拔高度是 0, 4, 1, 8 。1 当日地壳形变后,高程分别为 0, 6, 3, 8变为。此时,重点是 0, 1, 2, 3 处的风温为 0, -6, 0, -5 变为。


入力例 2

2 2 5 5
0
6
-1
1 1 4
1 2 8

出力例 2

5
-35

此输入示例是一个小作业。 2 满足条件。


入力例 3

7 8 8 13
0
4
-9
4
-2
3
10
-9
1 4 8
3 5 -2
3 3 9
1 7 4
3 5 -1
5 6 3
4 4 9
6 7 -10

出力例 3

277
277
322
290
290
290
290
370