#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=2e5+5, sx=2, inf=1e9;
int n, q, idx, df[nx], v[nx], l, r, x;
struct segtree
{
struct mat:array<array<ll, sx>, sx>
{
mat() {
for (int i=0; i<sx; i++) for (int j=0; j<sx; j++) (*this)[i][j]=-inf;
}
mat(int idx)
{
(*this)[1][1]=-inf; (*this)[0][1]=0;
if ((df[idx]^df[idx-1])>=0) (*this)[0][0]=abs(df[idx]), (*this)[1][0]=-inf;
else (*this)[0][0]=0, (*this)[1][0]=abs(df[idx]);
}
friend mat operator*(const mat A, const mat B)
{
mat res;
for (int i=0; i<sx; i++) for (int j=0; j<sx; j++) for (int k=0; k<sx; k++) res[i][j]=max(A[i][k]+B[k][j], res[i][j]);
return res;
}
} d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return void(d[i]=mat(l));
int md=(l+r)/2;
build(md+1, r, 2*i+1);
build(l, md, 2*i);
d[i]=d[2*i]*d[2*i+1];
}
void update(int l, int r, int i, int idx)
{
if (idx<l||r<idx) return;
if (l==r) return void(d[i]=mat(l));
int md=(l+r)/2;
update(l, md, 2*i, idx);
update(md+1, r, 2*i+1, idx);
d[i]=d[2*i]*d[2*i+1];
}
} s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>q;
for (int i=1; i<=n; i++) cin>>v[i], df[i]=v[i]-v[i-1];
s.build(2, n, 1);
while (q--)
{
cin>>l>>r>>x;
df[l]+=x; df[r+1]-=x;
s.update(2, n, 1, l);
s.update(2, n, 1, l+1);
s.update(2, n, 1, r+1);
s.update(2, n, 1, r+2);
cout<<max(s.d[1][0][0], s.d[1][1][0])<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
25300 KB |
Output is correct |
2 |
Correct |
9 ms |
25384 KB |
Output is correct |
3 |
Correct |
9 ms |
25300 KB |
Output is correct |
4 |
Correct |
9 ms |
25300 KB |
Output is correct |
5 |
Correct |
9 ms |
25300 KB |
Output is correct |
6 |
Correct |
9 ms |
25360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
25300 KB |
Output is correct |
2 |
Correct |
9 ms |
25384 KB |
Output is correct |
3 |
Correct |
9 ms |
25300 KB |
Output is correct |
4 |
Correct |
9 ms |
25300 KB |
Output is correct |
5 |
Correct |
9 ms |
25300 KB |
Output is correct |
6 |
Correct |
9 ms |
25360 KB |
Output is correct |
7 |
Correct |
13 ms |
25456 KB |
Output is correct |
8 |
Correct |
13 ms |
25432 KB |
Output is correct |
9 |
Correct |
14 ms |
25428 KB |
Output is correct |
10 |
Correct |
14 ms |
25516 KB |
Output is correct |
11 |
Correct |
13 ms |
25428 KB |
Output is correct |
12 |
Correct |
13 ms |
25516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
25300 KB |
Output is correct |
2 |
Correct |
9 ms |
25384 KB |
Output is correct |
3 |
Correct |
9 ms |
25300 KB |
Output is correct |
4 |
Correct |
9 ms |
25300 KB |
Output is correct |
5 |
Correct |
9 ms |
25300 KB |
Output is correct |
6 |
Correct |
9 ms |
25360 KB |
Output is correct |
7 |
Correct |
13 ms |
25456 KB |
Output is correct |
8 |
Correct |
13 ms |
25432 KB |
Output is correct |
9 |
Correct |
14 ms |
25428 KB |
Output is correct |
10 |
Correct |
14 ms |
25516 KB |
Output is correct |
11 |
Correct |
13 ms |
25428 KB |
Output is correct |
12 |
Correct |
13 ms |
25516 KB |
Output is correct |
13 |
Correct |
505 ms |
35968 KB |
Output is correct |
14 |
Correct |
466 ms |
36024 KB |
Output is correct |
15 |
Correct |
462 ms |
35980 KB |
Output is correct |
16 |
Correct |
489 ms |
36112 KB |
Output is correct |
17 |
Correct |
477 ms |
35884 KB |
Output is correct |
18 |
Correct |
487 ms |
36616 KB |
Output is correct |