AT_joi2017ho_a フェーン現象 (Foehn Phenomena)

### 题目简述 你知道$N+1$个地点的海拔$A_i$,编号为$0 \dots N$,有风从$0$吹向$N$,想让你求出地点$N$的风的温度. 保证$A_0=0$ 规则： - 如果$A_i=A_{i+1}$风的温度不变. - 如果$A_i>A_{i+1}$由于海拔降低,风的温度会上升$(A_i-A_{i+1})\times T$度 - 如果$A_i

无

无

### 課題 地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 $ 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 点\] - 追加の制限はない． - - - - - - ### Sample Explanation 1 最初，地点 $ 0,\ 1,\ 2,\ 3 $ の標高はそれぞれ $ 0,\ 4,\ 1,\ 8 $ である．$ 1 $ 日目の地殻変動の後，標高はそれぞれ $ 0,\ 6,\ 3,\ 8 $となる．このとき，地点 $ 0,\ 1,\ 2,\ 3 $ での風の温度はそれぞれ $ 0,\ -6,\ 0,\ -5 $ となる． - - - - - - ### Sample Explanation 2 この入力例は，小課題 $ 2 $ の条件を満たす． - - - - - -