#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,m;
int D[maxn];
struct node
{
int pre,suf,val_l,val_r,ans,sz;
};
inline node hop(node x, node y)
{
if (x.val_l==-1e18) return y;
if (y.val_l==-1e18) return x;
node z;
z.pre = x.pre;
if (x.pre==x.sz&&x.val_r==y.val_l) z.pre = max(z.pre,x.sz+y.pre);
z.suf = y.suf;
if (y.suf==y.sz&&y.val_l==x.val_r) z.suf = max(z.suf,y.sz+x.suf);
z.val_l = x.val_l; z.val_r = y.val_r;
z.ans = max(x.ans, y.ans);
if (x.val_r==y.val_l) z.ans = max(z.ans,x.suf+y.pre);
z.sz = x.sz + y.sz;
return z;
}
node f[4*maxn]; int lazy_sum[4*maxn], lazy_eq[4*maxn];
void pusheq(int x, int lx, int rx, int val)
{
f[x].val_l = f[x].val_r = lazy_eq[x] = val; lazy_sum[x]=0;
f[x].ans = f[x].pre = f[x].suf = f[x].sz = (rx-lx+1);
}
void pushsum(int x, int lx, int rx, int val)
{
f[x].val_l += val; f[x].val_r += val; lazy_sum[x] += val;
}
void down(int x, int lx, int rx)
{
if (lx==rx) return;
int mid=(lx+rx)/2;
if (lazy_eq[x]!=-1e18)
{
pusheq(2*x,lx,mid,lazy_eq[x]);
pusheq(2*x+1,mid+1,rx,lazy_eq[x]);
lazy_eq[x]=-1e18;
}
if (lazy_sum[x]!=0)
{
pushsum(2*x,lx,mid,lazy_sum[x]);
pushsum(2*x+1,mid+1,rx,lazy_sum[x]);
lazy_sum[x]=0;
}
}
void add(int x, int lx, int rx, int l, int r, int val)
{
if (lx>r||rx<l) return ;
if (lx>=l&&rx<=r)
{
pushsum(x,lx,rx,val);
return;
}
int mid=(lx+rx)/2;
down(x,lx,rx);
add(2*x,lx,mid,l,r,val);
add(2*x+1,mid+1,rx,l,r,val);
f[x]=hop(f[2*x],f[2*x+1]);
}
void update_eq(int x, int lx, int rx, int l, int r, int val)
{
if (lx>r||rx<l) return ;
if (lx>=l&&rx<=r)
{
pusheq(x,lx,rx,val);
return;
}
int mid=(lx+rx)/2; down(x,lx,rx);
update_eq(2*x,lx,mid,l,r,val);
update_eq(2*x+1,mid+1,rx,l,r,val);
f[x]=hop(f[2*x],f[2*x+1]);
}
void update(int x, int lx, int rx, int idx, int val)
{
if (lx==rx)
{
pusheq(x,lx,rx,val);
return;
}
int mid=(lx+rx)/2;
down(x,lx,rx);
if (idx<=mid) update(2*x,lx,mid,idx,val);
else update(2*x+1,mid+1,rx,idx,val);
f[x]=hop(f[2*x],f[2*x+1]);
}
node get(int x, int lx, int rx, int l, int r)
{
if (lx>r||rx<l) return {0,0,(int)-1e18,(int)-1e18,0,0};
if (lx>=l&&rx<=r) return f[x];
int mid=(lx+rx)/2;
down(x,lx,rx);
return hop(get(2*x,lx,mid,l,r),get(2*x+1,mid+1,rx,l,r));
}
struct line
{
int a,b;
};
inline int calc(line x, int idx)
{
return x.a*idx + x.b;
}
line seg[4*maxn],lazyeq[4*maxn],lazysum[4*maxn];
void pusheq_lichao(int x, int lx, int rx, line val)
{
seg[x]=lazyeq[x]=val; lazysum[x]={0,0};
}
void pushsum_lichao(int x, int lx, int rx, line val)
{
seg[x].a+=val.a; seg[x].b+=val.b;
lazysum[x].a+=val.a; lazysum[x].b+=val.b;
}
void down_lichao(int x, int lx, int rx)
{
if (lx==rx) return;
int mid=(lx+rx)/2;
if (lazyeq[x].a!=-1e18)
{
pusheq_lichao(2*x,lx,mid,lazyeq[x]);
pusheq_lichao(2*x+1,mid+1,rx,lazyeq[x]);
lazyeq[x]={(int)-1e18,(int)-1e18};
}
if (lazysum[x].a!=0||lazysum[x].b!=0)
{
pushsum_lichao(2*x,lx,mid,lazysum[x]);
pushsum_lichao(2*x+1,mid+1,rx,lazysum[x]);
lazysum[x]={0,0};
}
}
void add_lichao(int x, int lx, int rx, int l, int r, line val)
{
if (lx>r||rx<l) return ;
if (lx>=l&&rx<=r)
{
pushsum_lichao(x,lx,rx,val);
return;
}
int mid=(lx+rx)/2;
down_lichao(x,lx,rx);
add_lichao(2*x,lx,mid,l,r,val);
add_lichao(2*x+1,mid+1,rx,l,r,val);
}
void update_lichao(int x, int lx, int rx, int l, int r, line val)
{
if (lx>r||rx<l) return;
if (lx>=l&&rx<=r)
{
pusheq_lichao(x,lx,rx,val);
return;
}
int mid=(lx+rx)/2;
down_lichao(x,lx,rx);
update_lichao(2*x,lx,mid,l,r,val);
update_lichao(2*x+1,mid+1,rx,l,r,val);
}
line qry(int x, int lx, int rx, int idx)
{
if (lx==rx) return seg[x];
int mid=(lx+rx)/2;
down_lichao(x,lx,rx);
if (idx<=mid) return qry(2*x,lx,mid,idx);
else return qry(2*x+1,mid+1,rx,idx);
}
void build(int x, int lx, int rx)
{
lazy_eq[x]=-1e18;
lazy_sum[x]=0;
if (lx==rx)
{
pusheq(x,lx,rx,D[lx]-D[lx-1]);
return;
}
int mid=(lx+rx)/2;
build(2*x,lx,mid); build(2*x+1,mid+1,rx);
f[x]=hop(f[2*x],f[2*x+1]);
}
void build_lichao(int x, int lx, int rx)
{
lazyeq[x]={(int)-1e18,(int)-1e18};
lazysum[x]={0,0};
if (lx==rx)
{
pusheq_lichao(x,lx,rx,{0,D[lx]});
return;
}
int mid=(lx+rx)/2;
build_lichao(2*x,lx,mid); build_lichao(2*x+1,mid+1,rx);
}
//void dbg(int x, int lx, int rx)
//{
// cout<<x<<' '<<lx<<' '<<rx<<" = "<<f[x].val_l<<' '<<f[x].val_r<<" , "<<f[x].pre<<' '<<f[x].suf<<" , "<<f[x].sz<<' '<<f[x].ans<<" :: "<<lazy_eq[x]<<' '<<lazy_sum[x]<<'\n';
// if (lx==rx) return;
// int mid=(lx+rx)/2;
// dbg(2*x,lx,mid);
// dbg(2*x+1,mid+1,rx);
//}
//void dbg_lichao(int x, int lx, int rx)
//{
// cout<<x<<' '<<lx<<' '<<rx<<" = "<<seg[x].a<<' '<<seg[x].b<<" , "<<lazysum[x].a<<' '<<lazysum[x].b<<" , "<<lazyeq[x].a<<' '<<lazyeq[x].b<<'\n';
// if (lx==rx) return;
// int mid=(lx+rx)/2;
// dbg_lichao(2*x,lx,mid);
// dbg_lichao(2*x+1,mid+1,rx);
//}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n>>m;
for (int i=1; i<=n; i++) cin>>D[i];
build(1,2,n);
build_lichao(1,1,n);
for (int i=1; i<=m; i++)
{
int t; cin>>t;
if (t==1)
{
int l,r,S,C; cin>>l>>r>>S>>C;
line temp = {C, S-l*C};
add(1,2,n,l+1,r,C);
add_lichao(1,1,n,l,r,temp);
if (l>1) update(1,2,n,l,calc(qry(1,1,n,l),l) - calc(qry(1,1,n,l-1),l-1));
if (r<n) update(1,2,n,r+1,calc(qry(1,1,n,r+1),r+1) - calc(qry(1,1,n,r),r));
// cout<<l<<" :: "<<calc(qry(1,1,n,l),l)<<'\n';
// cout<<r<<" :: "<<calc(qry(1,1,n,r),r)<<'\n';
}
else if (t==2)
{
int l,r,S,C; cin>>l>>r>>S>>C;
line temp = {C, S-l*C};
update_eq(1,2,n,l+1,r,C);
update_lichao(1,1,n,l,r,temp);
if (l>1) update(1,2,n,l,calc(qry(1,1,n,l),l) - calc(qry(1,1,n,l-1),l-1));
if (r<n) update(1,2,n,r+1,calc(qry(1,1,n,r+1),r+1) - calc(qry(1,1,n,r),r));
}
else
{
int l,r; cin>>l>>r;
node temp = get(1,1,n,l+1,r);
int ans = temp.ans + 1;
cout<<ans<<'\n';
}
// dbg(1,2,n);
// cout<<" ========= \n";
// dbg_lichao(1,1,n);
// cout<<"---------------------------\n";
// cout<<"---------------------------\n";
// cout<<"---------------------------\n";
}
}
/**
10 3
1 2 3 4 1 2 3 4 5 5
3 1 10
1 2 8 1 2
3 2 9
2 1 10 3 4
3 1 10
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
115344 KB |
Output is correct |
| 2 |
Correct |
84 ms |
2400 KB |
Output is correct |
| 3 |
Correct |
96 ms |
2340 KB |
Output is correct |
| 4 |
Correct |
86 ms |
2380 KB |
Output is correct |
| 5 |
Correct |
90 ms |
2516 KB |
Output is correct |
| 6 |
Incorrect |
84 ms |
2416 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
115808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
768 ms |
114428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
115808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
115344 KB |
Output is correct |
| 2 |
Correct |
84 ms |
2400 KB |
Output is correct |
| 3 |
Correct |
96 ms |
2340 KB |
Output is correct |
| 4 |
Correct |
86 ms |
2380 KB |
Output is correct |
| 5 |
Correct |
90 ms |
2516 KB |
Output is correct |
| 6 |
Incorrect |
84 ms |
2416 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
