#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl;
#define B17 ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define ll long long int
using namespace std;
const int maxn = 2e5 + 10;
int n , q;
int a[maxn] , st[maxn] , jo[maxn];
ll dp[maxn] , ans;
bool cut[maxn];
int l , r, x;
void fixl(int i){
int oj = jo[i];
bool rev = 0;
if(x < 0){
if(st[i] == -1){
jo[i] += -x;
}
else{
jo[i] -= -x;
if(jo[i] < 0){
rev = 1;
jo[i] *= -1;
st[i] *= -1;
}
}
}
else{
if(st[i] == 1){
jo[i] += x;
}
else{
jo[i] -= x;
if(jo[i] < 0){
rev = 1;
jo[i] *= -1;
st[i] *= -1;
}
}
}
if(cut[i] == 0){
ans -= oj;
ans += jo[i];
}
else if(cut[i] == 1){
if(st[i] == 1){
if(jo[i + 1] < jo[i]){
ans += jo[i];
ans -= jo[i + 1];
cut[i] = 0;
cut[i + 1] = 1;
}
}//hal
else{
if(rev)ans += jo[i];
}
}
else{
if(st[i] == 1){
}
}
}
void solv(){
int l , r , x;
cin >> l >> r >> x;
ans = 0;
for(int i = 1; i <= n; i++){
cut[i] = 0;
if(i >= l && i <= r)a[i] += x;
if(i > 1)jo[i] = abs(a[i] - a[i - 1]);
if(i > 1)if(a[i] > a[i - 1])st[i] = 1;//st[i] 1 he age i bozorge bashe jo[i] , va bar aks
else st[i] = -1;
ans += jo[i];
}
for(int i = 2; i < n; i++){
if(!cut[i] && a[i] > a[i - 1] && a[i] > a[i + 1]){
ans -= min(jo[i] , jo[i + 1]);
if(jo[i + 1] > jo[i])cut[i] = 1;
else cut[i + 1] = 1;
}
else if(!cut[i] && a[i] < a[i - 1] && a[i] < a[i + 1]){
ans -= min(jo[i] , jo[i + 1]);
if(jo[i + 1] > jo[i])cut[i] = -1;
else cut[i + 1] = -1;
}
}
cout << ans << endl;
}
int main(){
B17;
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(i > 1)jo[i] = abs(a[i] - a[i - 1]);
if(i > 1)if(a[i] > a[i - 1])st[i] = 1;//st[i] 1 he age i bozorge bashe jo[i] , va bar aks
else st[i] = -1;
ans += jo[i];
}
for(int i = 2; i < n; i++){
if(!cut[i] && a[i] > a[i - 1] && a[i] > a[i + 1]){
ans -= min(jo[i] , jo[i + 1]);
if(jo[i + 1] > jo[i])cut[i] = 1;
else cut[i + 1] = 1;
}
else if(!cut[i] && a[i] < a[i - 1] && a[i] < a[i + 1]){
ans -= min(jo[i] , jo[i + 1]);
if(jo[i + 1] > jo[i])cut[i] = -1;
else cut[i + 1] = -1;
}
}
// cout << ans << endl;
while(q--){
solv();
}
}
/* temp
4 3
2 0 2 1
4 4 1
2 2 3
1 3 2
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
6 5
2 4 2 4 2 4
1 1 0
5 5
2 4 3 4 5
1 1 0
*/
Compilation message
Main.cpp: In function 'void solv()':
Main.cpp:74:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
74 | if(i > 1)if(a[i] > a[i - 1])st[i] = 1;//st[i] 1 he age i bozorge bashe jo[i] , va bar aks
| ^
Main.cpp: In function 'int main()':
Main.cpp:99:11: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
99 | if(i > 1)if(a[i] > a[i - 1])st[i] = 1;//st[i] 1 he age i bozorge bashe jo[i] , va bar aks
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
