#include<bits/stdc++.h>
using namespace std;
int inf=1e9;
struct segtree{
struct node{
int pre,suf,vpre,vsuf,mx,sz;
node(int x=0){
pre=suf=0;
mx=1;
vpre=vsuf=x;
}
friend node operator+(node a,node b){
node c;
c.vpre=a.vpre;
if(a.pre==a.sz&&a.vpre==b.vpre)c.pre=a.pre+b.pre;
else c.pre=a.pre;
c.vsuf=b.vsuf;
if(b.suf==b.sz&&b.vsuf==a.vsuf)c.suf=a.suf+b.suf;
else c.suf=b.suf;
c.mx=max({a.mx,b.mx,(a.vsuf==b.vpre?a.suf+b.pre:0)});
c.sz=a.sz+b.sz;
return c;
}
};
node info[1200005];
int lset[1200005];
int lmath[1200005];
void push(int st,int en,int i){
if(lset[i]!=0){
info[i].pre=info[i].suf=info[i].mx=info[i].sz;
info[i].vpre=info[i].vsuf=0;
if(st!=en)lset[i*2]=lset[i*2+1]=lset[i],lmath[i*2]=lmath[i*2+1]=0;
lset[i]=0;
}
if(lmath[i]!=0){
info[i].vpre+=lmath[i];
info[i].vsuf+=lmath[i];
if(st!=en)lmath[i*2]+=lmath[i],lmath[i*2+1]+=lmath[i];
lmath[i]=0;
}
}
void upd(int st,int en,int i,int pos,int val){
if(st>pos||en<pos)return;
//cerr<<st<<" "<<en<<" "<<i<<"\n";
push(st,en,i);
if(st==en){
//cerr<<"yes:"<<val<<"\n";
info[i].vpre+=val;
info[i].vsuf+=val;
//cerr<<info[i].vpre<<"\n";
return;
}
int m=(st+en)/2;
upd(st,m,i*2,pos,val);
upd(m+1,en,i*2+1,pos,val);
info[i]=info[i*2]+info[i*2+1];
}
void upd_set(int st,int en,int i,int l,int r){
if(st>r||en<l)return;
push(st,en,i);
if(st>=l&&en<=r){
lset[i]=1;
push(st,en,i);
return;
}
int m=(st+en)/2;
upd_set(st,m,i*2,l,r);
upd_set(m+1,en,i*2+1,l,r);
info[i]=info[i*2]+info[i*2+1];
}
void upd_math(int st,int en,int i,int l,int r,int val){
if(st>r||en<l)return;
push(st,en,i);
if(st>=l&&en<=r){
lmath[i]+=val;
push(st,en,i);
return;
}
int m=(st+en)/2;
upd_math(st,m,i*2,l,r,val);
upd_math(m+1,en,i*2+1,l,r,val);
}
node fval(int st,int en,int i,int l,int r){
push(st,en,i);
if(st==en)return info[i];
int m=(st+en)/2;
if(l<=m&&r>m)return fval(st,m,i*2,l,r)+fval(m+1,en,i*2+1,l,r);
else if(l>m)return fval(m+1,en,i*2+1,l,r);
else return fval(st,m,i*2,l,r);
}
void build(int st,int en,int i){
if(st==en){
info[i].pre=info[i].suf=info[i].mx=info[i].sz=1;
info[i].vpre=info[i].vsuf=0;
return;
}
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
info[i]=info[i*2]+info[i*2+1];
}
}tr;
struct segvaltree{
int info[1200005];
int math[1200005];
int add[1200005];
int set[1200005];
void push(int st,int en,int i){
if(set[i]!=0){
if(st==en)info[i]=0;
else {
set[i*2]=set[i*2+1]=set[i];
math[i*2]=math[i*2+1]=add[i*2]=add[i*2+1]=0;
}
set[i]=0;
}
if(math[i]!=0){
if(st!=en){
math[i*2]+=math[i];
math[i*2+1]+=math[i];
add[i*2+1]+=((st+en)/2-st+1)*math[i];
}
math[i]=0;
}
if(add[i]!=0){
if(st==en)info[i]+=add[i];
else{
add[i*2]+=add[i];
add[i*2+1]+=add[i];
}
add[i]=0;
}
}
void upd_set(int st,int en,int i,int l,int r){
if(st>r||en<l)return;
push(st,en,i);
if(st>=l&&en<=r){
set[i]=1;
push(st,en,i);
return;
}
int m=(st+en)/2;
upd_set(st,m,i*2,l,r);
upd_set(m+1,en,i*2+1,l,r);
}
void upd_add(int st,int en,int i,int l,int r,int val){
//cerr<<st<<" "<<en<<" "<<i<<" "<<l<<" "<<r<<"\n";
if(st>r||en<l)return;
push(st,en,i);
if(st>=l&&en<=r){
//cerr<<"yes"<<"\n";
add[i]=val;
push(st,en,i);
return;
}
int m=(st+en)/2;
upd_add(st,m,i*2,l,r,val);
upd_add(m+1,en,i*2+1,l,r,val);
}
void upd_math(int st,int en,int i,int l,int r,int val,int begin){
if(st>r||en<l)return;
push(st,en,i);
if(st>=l&&en<=r){
math[i]=val;
int dif=st-begin;
add[i]=dif*val;
push(st,en,i);
return;
}
int m=(st+en)/2;
upd_math(st,m,i*2,l,r,val,begin);
upd_math(m+1,en,i*2+1,l,r,val,begin);
}
int find(int st,int en,int i,int pos){
push(st,en,i);
int m=(st+en)/2;
if(st==en)return info[i];
if(pos<=m)return find(st,m,i*2,pos);
else return find(m+1,en,i*2+1,pos);
}
}val;
int ar[300005];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>ar[i];
val.upd_add(1,n,1,i,i,ar[i]);
//for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
//cerr<<"\n";
}
tr.build(1,n-1,1);
/*cerr<<"INFO BF UPD:\n";
for(int i=1;i<n;i++){
cerr<<tr.fval(1,n-1,1,i,i).vpre<<" "<<tr.fval(1,n-1,1,i,i).mx<<"\n";
}
cerr<<"\n";
cerr<<"UPDATING:\n";*/
for(int i=1;i<n;i++){
//cerr<<"I:"<<i<<"\n";
tr.upd(1,n-1,1,i,ar[i+1]-ar[i]);
//cerr<<"\n";
//cerr<<i<<" "<<ar[i+1]-ar[i]<<" "<<tr.fval(1,n-1,1,i,i).vpre<<"\n";
}
//tr.upd(1,n,1,n,-inf);
/*cerr<<"DIF:\n";
for(int i=1;i<=n;i++){
cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
}*/
//cerr<<"\n";
//for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
//cerr<<"\n\n\n";
for(int i=0;i<q;i++){
int x;cin>>x;
if(x==1){
int l,r,s,c;cin>>l>>r>>s>>c;
//cerr<<"I:"<<i<<" "<<l<<" "<<r<<" "<<s<<" "<<c<<"\n";
int bf=val.find(1,n,1,l-1);
int curl=val.find(1,n,1,l);
int af=val.find(1,n,1,r+1);
int curr=val.find(1,n,1,r);
int curdifl=tr.fval(1,n-1,1,l,l).vpre;
int curdifr=tr.fval(1,n-1,1,r,r).vpre;
//cerr<<bf<<" "<<curl<<" "<<af<<" "<<curr<<"\n";
tr.upd(1,n-1,1,l-1,curl+s-bf-curdifl);
//cerr<<"tree upd:"<<af-curr-s-c*(r-l)-curdifr<<"\n";
tr.upd(1,n-1,1,r,af-curr-s-c*(r-l)-curdifr);
//for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
//cerr<<"\n";
tr.upd_math(1,n-1,1,l,r-1,c);
val.upd_add(1,n,1,l,r,s);
//cerr<<"val:"<<curr+s+c*(r-l)<<"\n";
//cerr<<"after add: ";
//for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
//cerr<<"\n";
val.upd_math(1,n,1,l,r,c,l);
//cerr<<"after math: ";
//for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
//cerr<<"\n";
}else if(x==2){
//cerr<<"REWRITE\n";
int l,r,s,c;cin>>l>>r>>s>>c;
int bf=val.find(1,n,1,l-1);
int af=val.find(1,n,1,r+1);
int curdifl=tr.fval(1,n-1,1,l,l).vpre;
int curdifr=tr.fval(1,n-1,1,r,r).vpre;
//cerr<<"bf,af:"<<bf<<" "<<af<<"\n";
tr.upd_set(1,n-1,1,l,r-1);
//cerr<<"after set:\n";
//for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
// cerr<<"\n";
tr.upd(1,n-1,1,l-1,s-bf-curdifl);
tr.upd(1,n-1,1,r,af-s-c*(r-l)-curdifr);
//for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
tr.upd_math(1,n-1,1,l,r-1,c);
val.upd_set(1,n,1,l,r);
val.upd_add(1,n,1,l,r,s);
val.upd_math(1,n,1,l,r,c,l);
//the gap may fluctuated in different ways depending on which index is bigger
}else{
int l,r;cin>>l>>r;
cout<<tr.fval(1,n-1,1,l,r).mx+1<<"\n";
}
//cerr<<"AFTER EVERYTHING:\n";
//for(int i=1;i<=n;i++)cerr<<tr.fval(1,n-1,1,i,i).vpre<<" ";
//cerr<<"\n";
//cerr<<tr.fval(1,n-1,1,1,n).mx<<"\n";
//for(int i=1;i<=n;i++)cerr<<val.find(1,n,1,i)<<" ";
//cerr<<"ALL\n";
//cerr<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3059 ms |
46168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
33624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
930 ms |
46656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1708 ms |
55012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
930 ms |
46656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3059 ms |
46168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
