フェーン現象 (Foehn Phenomena)

题意翻译

题目简述

你知道N+1N+1个地点的海拔A_iAi​,编号为0 dots N0…N,有风从00吹向NN,想让你求出地点NN的风的温度.

保证A_0=0A0​=0

规则：

• 如果A_i=A_{i+1}Ai​=Ai+1​风的温度不变.
• 如果A_i>A_{i+1}Ai​>Ai+1​由于海拔降低,风的温度会上升(A_i-A_{i+1}) imes T(Ai​−Ai+1​)×T度
• 如果A_i<A_{i+1}Ai​<Ai+1​由于海拔升高,风的温度会下降(A_{i+1}-A_i) imes S(Ai+1​−Ai​)×S度

输入格式：

从标准输入中读入下面的数据.

• 第一行输入包括四个被空格隔开的整数N,Q,S,TN,Q,S,T.这表示JOI先生在地点NN有一所房子,有QQ次地壳运动,海拔每上升1米的话,风的温度会降低SS度,海拔每下降一米的话,风的温度会上升TT度.
• 接下来的N+1N+1行中第ii行(1leq ileq N+1)(1≤i≤N+1)包含一个整数A_{i-1}Ai−1​,表示地壳运动前地点i-1i−1的海拔高度.
• 接下来的QQ行中第jj行(1leq jleq Q)(1≤j≤Q)包括三个被空格隔开的整数L_j,R_j,X_jLj​,Rj​,Xj​.这表示第jj天地壳运动使地点L_jLj​到地点R_jRj​中这些地点的海拔变化了X_jXj​

输出格式:

输出QQ行,第jj行的输出代表第jj天地壳运动后JOI先生家的风的温度. (即NN位置的风的温度)

题目描述

 

输入格式

Read the following data from the standard input.

• The first line of input contains four space separated integers N,Q,S,TN,Q,S,T . This means there is a house of Mr. JOI at Spot NN , there are QQ tectonic movements, the temperature of the wind decreases by SS degrees per altitude if the altitude increases, and the temperature of the wind increases by TT degrees per altitude if the altitude decreases.
• The ii -th line (1 leq i leq N+1)(1 ≤ i ≤ N+1) of the following N+1N+1 lines contains an integer A_{i−1} , which is the initial altitude at Spot (i − 1) before tectonic movements.
• The jj -th line (1 leq j leq Q)(1 ≤ j ≤ Q) of the following QQ lines contains three space separated integers L_j, R_j, X_jLj​, Rj​, Xj​ . This means, for the tectonic movement on the jj -th day, the change of the altitude at the spots from L_jLj​ to R_jRj​ is described by X_jXj​ .

输出格式

Write QQ lines to the standard output. The jj -th line (1 leq j leq Q)(1 ≤ j ≤ Q) of output contains the temperature of the wind at the house of Mr. JOI after the tectonic movement on the jj -th day.

输入输出样例

输入 #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

输入 #2复制

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

输出 #2复制

5
-35

输入 #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

输入 #4复制

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

输出 #4复制

-5
-7
-13
-13
-18

输入 #5复制

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

输出 #5复制

5
-35

输入 #6复制

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

输出 #6复制

277
277
322
290
290
290
290
370

说明/提示

課題

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

制限

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

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

Task

Given the data of tectonic movements, write a program which calculates, for each j (1 leq j leq Q)j (1 ≤ j ≤ Q) . the temperature of the wind at the house of Mr. JOI after the tectonic movement on the jj -th day.

Constraints

All input data satisfy the following conditions.

• 1 leq N leq 200\,0001 ≤ N ≤ 200000 .
• 1 leq Q leq 200\,0001 ≤ Q ≤ 200000 .
• 1 leq S leq 1\,000\,0001 ≤ S ≤ 1000000 .
• 1 leq T leq 1\,000\,0001 ≤ T ≤ 1000000 .
• A_0 = 0A0​ = 0 .
• −1\,000\,000 leq A_i leq 1\,000\,000 (1 leq i leq N) .
• 1 leq L_j leq R_j leq N (1 leq j leq Q)1 ≤ Lj​ ≤ Rj​ ≤ N (1 ≤ j ≤ Q) .
• −1\,000\,000 leq X_j leq 1\,000\,000 (1 leq j leq Q) .

Sample Explanation 1

最初，地点 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 となる．

Sample Explanation 2

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

Sample Explanation 4

Initially, the altitudes of the spot 0,1,2,30,1,2,3 are 0, 4, 1, 80, 4, 1, 8 , respectively. After the tectonic movement on the first day, the altitudes become 0, 6, 3, 80, 6, 3, 8 , respectively. At that moment, the temperatures of the wind are 0, -6, 0, 50, −6, 0, 5 , respectively.

Sample Explanation 5

This sample input satisfies the constrains of Subtask 2.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll s1,s2;
ll dif[300001];
ll get(ll t)
{
    if(t>0)return -s1*t;
    else return -s2*t;
}
int main()
{
    int num,query;
    scanf("%d%d%lld%lld",&num,&query,&s1,&s2);
    vector<int>v;
    for(int i=0;i<=num;i++)
    {
        int z;
        scanf("%d",&z);
        v.push_back(z);
    }
    ll ans=0;
    for(int i=0;i<num;i++)
    {
        dif[i]=v[i+1]-v[i];
        ans+=get(dif[i]);
    }
    for(int i=0;i<query;i++)
    {
        int za,zb,zc;
        scanf("%d%d%d",&za,&zb,&zc);
        ans-=get(dif[za-1]);
        dif[za-1]+=zc;
        ans+=get(dif[za-1]);
        if(zb!=num)
        {
            ans-=get(dif[zb]);
            dif[zb]-=zc;
            ans+=get(dif[zb]);
        }
        printf("%lld
",ans);
    }
    return 0;
}