A - フェーン現象 (Foehn Phenomena) Editorial

Time Limit: 1 sec / Memory Limit: 256 MB

配点： 100100 点

IOI 国では海から陸に向かって常に風が吹いている．風は地点 00 から地点 11，地点 22，…\ldots という経路を通りながら地点 NN まで吹く．地点 NN には JOI 君の家が建てられている．地点 00 の標高は A0=0A_0 = 0 であり，地点 ii (1≦i≦N1 \leqq i \leqq N) の標高は AiA_i である．

風は地表面に沿って吹き，高度の変化に応じて風の温度が変化する．海に接している地点 00 での風の温度は 00 度であり，すべての ii (0≦i≦N−10 \leqq i \leqq N - 1) に対して，地点 ii から地点 i+1i + 1 にかけての風の温度の変化はその時点における AiA_i と Ai+1A_{i + 1} にのみ依存しており，以下のようになっている．

  • Ai<Ai+1A_i < A_{i + 1} のとき，標高が 11 上がるごとに風の温度は SS 度下がる．
  • Ai≧Ai+1A_i \geqq A_{i + 1} のとき，標高が 11 下がるごとに風の温度は TT 度上がる．

IOI 国の領土では地殻変動が盛んである．あなたは，QQ 日間の地殻変動のデータを入手した．jj 日目 (1≦j≦Q1 \leqq j \leqq Q) には，Lj≦k≦RjL_j \leqq k \leqq R_j (1≦Lj≦Rj≦N1 \leqq L_j \leqq R_j \leqq N) を満たす地点の標高 AkA_k が XjX_j だけ変化する．XjX_j が非負のときは，標高が XjX_j だけ上がることを意味し，XjX_j が負のときは，標高が ∣Xj∣|X_j| だけ下がることを意味する．

あなたの仕事は，各地殻変動が起こった後の，JOI 君の家に吹く風の温度を求めることである．

課題

地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 jj (1≦j≦Q1 \leqq j \leqq Q) に対し，jj 日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

  • 11 行目には， 44 個の整数 N,Q,S,TN, Q, S, T が空白を区切りとして書かれている．これらは，JOI 君の家が地点 NN に建てられており，地殻変動の回数が QQ であり，標高が 11 上がるごとに風の温度が SS 度下がり，11 下がるごとに TT 度上がることを表す．
  • 続く N+1N + 1 行のうちの ii 行目 (1≦i≦N+11 \leqq i \leqq N + 1) には，地点 i−1i - 1 での地殻変動が起こる前の標高を表す整数 Ai−1A_{i - 1} が書かれている．
  • 続く QQ 行のうちの jj 行目 (1≦j≦Q1 \leqq j \leqq Q) には，33 個の整数 Lj,Rj,XjL_j, R_j, X_j が空白を区切りとして書かれている．これらは，jj 日目の地殻変動で地点 LjL_j から RjR_j までの標高が XjX_j だけ変化することを表す．

出力

出力は QQ 行からなる．標準出力の jj 行目 (1≦j≦Q1 \leqq j \leqq Q) には，jj 日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を出力せよ．

制限

すべての入力データは以下の条件を満たす．

  • 1≦N≦200 0001 \leqq N \leqq 200\,000．
  • 1≦Q≦200 0001 \leqq Q \leqq 200\,000．
  • 1≦S≦1 000 0001 \leqq S \leqq 1\,000\,000．
  • 1≦T≦1 000 0001 \leqq T \leqq 1\,000\,000．
  • A0=0A_0 = 0．
  • −1 000 000≦Ai≦1 000 000-1\,000\,000 \leqq A_i \leqq 1\,000\,000 (1≦i≦N1 \leqq i \leqq N)．
  • 1≦Lj≦Rj≦N1 \leqq L_j \leqq R_j \leqq N (1≦j≦Q1 \leqq j \leqq Q)．
  • −1 000 000≦Xj≦1 000 000-1\,000\,000 \leqq X_j \leqq 1\,000\,000 (1≦j≦Q1 \leqq j \leqq Q)．

小課題

小課題 1 [30 点]

以下の条件を満たす．

  • N≦2 000N \leqq 2\,000．
  • Q≦2 000Q \leqq 2\,000．

小課題 2 [10 点]

  • S=TS = T を満たす．

小課題 3 [60 点]

  • 追加の制限はない．

入力例 1Copy

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

出力例 1Copy

Copy
-5
-7
-13
-13
-18

最初，地点 0,1,2,30, 1, 2, 3 の標高はそれぞれ 0,4,1,80, 4, 1, 8 である．11 日目の地殻変動の後，標高はそれぞれ 0,6,3,80, 6, 3, 8となる．このとき，地点 0,1,2,30, 1, 2, 3 での風の温度はそれぞれ 0,−6,0,−50, -6, 0, -5 となる．

入力例 2Copy

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

出力例 2Copy

Copy
5
-35

この入力例は，小課題 22 の条件を満たす．

入力例 3Copy

Copy
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

出力例 3Copy

Copy
277
277
322
290
290
290
290
370

2025-04-14 (Mon)
01:55:20 +00:00