#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long all[maxn],n,q,kaf=(1<<19);
struct node{
long long res00,res01,res10,res11;
node(){
res00=res01=res10=res11=0;
}
}fakenode;
struct fenwick{
long long fn[maxn];
fenwick(){
for(long long i=0;i<maxn;i++){
fn[i]=0;
}
}
void upd(long long i,long long w){
// //cout<<i<<" "<<w<<" upd"<<endl;
i++;
while(i<maxn){
fn[i]+=w;
i+=((-i)&i);
}
}
long long pors(long long i){
// //cout<<i<<" ";
i++;
long long ret=0;
while(i>0){
ret+=fn[i];
i-=((-i)&i);
}
// //cout<<ret<<" pors:"<<endl;
return ret;
}
}fen;
struct segment{
node seg[(1<<20)];
node merge(node a,node b){
node ret;
ret.res00=max(a.res01+b.res00,max(a.res00+b.res10,a.res00+b.res00));
ret.res10=max(a.res11+b.res00,max(a.res10+b.res10,a.res10+b.res00));
ret.res01=max(a.res01+b.res01,max(a.res00+b.res11,a.res00+b.res01));
ret.res11=max(a.res11+b.res01,max(a.res10+b.res11,a.res10+b.res01));
return ret;
}
void ins(long long i,long long w){
//cout<<"ins: "<<i<<" "<<w<<"\n";
i+=kaf;
seg[i].res00=seg[i].res10=seg[i].res01=seg[i].res11=w;
i>>=1;
while(i>0){
seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
void shart(long long i){
//cout<<"shart: "<<i<<"\n";
i+=kaf;
seg[i].res00=seg[i].res10=seg[i].res01=0;
i>>=1;
while(i>0){
seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
}seg;
void vorod(){
cin>>n>>q;
for(long long i=1;i<=n;i++){
cin>>all[i];
}
}
long long vas(long long l,long long r){
// //cout<<l<<" "<<r<<" "<<fen.pors(l)<<" "<<fen.pors(r)<<"\n";
if(fen.pors(l)<fen.pors(r)){
return -1;
}
if(fen.pors(l)==fen.pors(r)){
return 0;
}
return 1;
}
bool extreme(long long i){
if(i<=1||i>=n){
return 0;
}
if(vas(i-1,i)==vas(i+1,i)){
return 1;
}
return 0;
}
void ins(long long i){
if(i<1||i>n){
return ;
}
if(i>1){
seg.ins(i-1,abs(fen.pors(i)-fen.pors(i-1)));
}if(i<n){
seg.ins(i,abs(fen.pors(i+1)-fen.pors(i)));
}
if(extreme(i)||extreme(i-1)){
seg.shart(i-1);
}
if(extreme(i)||extreme(i+1)){
seg.shart(i);
}
}
void upd(long long l,long long r,long long w){
fen.upd(l,w);
fen.upd(r+1,-w);
ins(l);
ins(l-1);
ins(r);
ins(r+1);
}
void solve(){
for(long long i=1;i<=n;i++){
upd(i,i,all[i]);
}
for(long long i=0;i<q;i++){
long long l,r,w;
cin>>l>>r>>w;
// //cout<<"wtf: "<<l<<" "<<r<<" "<<w<<endl;
upd(l,r,w);
cout<<max(max(seg.seg[1].res00,seg.seg[1].res01),max(seg.seg[1].res10,seg.seg[1].res11))<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
////cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
35420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
35420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
35420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
