#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = (int)1e18;
const int maxn = 3e5 + 10;
int n,m;
int D[maxn];
struct node
{
int pre,suf,val_l,val_r,sz,ans;
};
node hop(node x, node y)
{
if (x.val_l==-1e18) return y;
if (y.val_l==-1e18) return x;
node cur;
cur.sz=x.sz+y.sz;
cur.ans=max(x.ans,y.ans);
if (x.val_r==y.val_l) cur.ans=max(cur.ans,x.suf+y.pre);
cur.val_l=x.val_l; cur.val_r=y.val_r;
if (x.sz==x.pre&&x.val_r==y.val_l) cur.pre=x.sz+y.pre;
else cur.pre=x.pre;
if (y.sz==y.suf&&x.val_l==y.val_r) cur.suf=y.sz+x.suf;
else cur.suf=y.suf;
return cur;
}
node none = {0,0,-inf,-inf,0,0};
struct segtree
{
node f[4*maxn]; int lazysum[4*maxn], lazyeq[4*maxn];
void pushsum(int x, int lx, int rx, int val)
{
f[x].val_l+=val; f[x].val_r+=val;
lazysum[x]+=val;
}
void pusheq(int x, int lx, int rx, int val)
{
f[x].val_l=f[x].val_r=lazyeq[x]=val;
f[x].ans=f[x].pre=f[x].suf=f[x].sz=rx-lx+1;
lazysum[x]=0;
}
void down(int x, int lx, int rx)
{
if (lx==rx) return;
int mid=(lx+rx)/2;
if (lazyeq[x]!=-1e18)
{
pusheq(2*x,lx,mid,lazyeq[x]);
pusheq(2*x+1,mid+1,rx,lazyeq[x]);
lazyeq[x]=-1e18;
}
if (lazysum[x]!=0)
{
pushsum(2*x,lx,mid,lazysum[x]);
pushsum(2*x+1,mid+1,rx,lazysum[x]);
lazysum[x]=0;
}
}
void build(int x, int lx, int rx)
{
lazysum[x]=0;
lazyeq[x]=-1e18;
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 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,-inf,-inf,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));
}
};
segtree tree;
struct line
{
int a,b;
};
int calc(line x, int idx)
{
return x.a*idx + x.b;
}
struct lichao_tree
{
line f[4*maxn],lazysum[4*maxn],lazyeq[4*maxn];
void pushsum(int x, int lx, int rx, line val)
{
f[x].a+=val.a; f[x].b+=val.b;
lazysum[x].a+=val.a; lazysum[x].b+=val.b;
}
void pusheq(int x, int lx, int rx, line val)
{
f[x]=lazyeq[x]=val; lazysum[x]={0,0};
}
void down(int x, int lx, int rx)
{
if (lx==rx) return;
int mid=(lx+rx)/2;
if (lazyeq[x].a!=-inf||lazyeq[x].b!=-inf)
{
pusheq(2*x,lx,mid,lazyeq[x]);
pusheq(2*x+1,mid+1,rx,lazyeq[x]);
lazyeq[x]={-inf,-inf};
}
if (lazysum[x].a!=0||lazysum[x].b!=0)
{
pushsum(2*x,lx,mid,lazysum[x]);
pushsum(2*x+1,mid+1,rx,lazysum[x]);
lazysum[x]={0,0};
}
}
void build(int x, int lx, int rx)
{
lazysum[x]={0,0};
lazyeq[x]={-inf,-inf};
if (lx==rx)
{
pusheq(x,lx,rx,{0,D[lx]});
return;
}
int mid=(lx+rx)/2;
build(2*x,lx,mid); build(2*x+1,mid+1,rx);
}
void add(int x, int lx, int rx, int l, int r, line 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);
}
void update_eq(int x, int lx, int rx, int l, int r, line 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);
}
line get(int x, int lx, int rx, int idx)
{
if (lx==rx) return f[x];
int mid=(lx+rx)/2;
down(x,lx,rx);
if (idx<=mid) return get(2*x,lx,mid,idx);
else return get(2*x+1,mid+1,rx,idx);
}
};
lichao_tree lichao;
void sub1()
{
for (int i=1; i<=m; i++)
{
int t; cin>>t;
if (t==1||t==2)
{
int l,r,x,y; cin>>l>>r>>x>>y;
}
else
{
int l,r; cin>>l>>r;
cout<<"1\n";
}
}
}
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];
if (n==1)
{
sub1();
return 0;
}
tree.build(1,2,n);
lichao.build(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};
tree.add(1,2,n,l+1,r,C);
lichao.add(1,1,n,l,r,temp);
if (l>1) tree.update(1,2,n,l,calc(lichao.get(1,1,n,l),l) - calc(lichao.get(1,1,n,l-1),l-1));
if (r<n) tree.update(1,2,n,r+1,calc(lichao.get(1,1,n,r+1),r+1) - calc(lichao.get(1,1,n,r),r));
}
else if (t==2)
{
int l,r,S,C; cin>>l>>r>>S>>C;
line temp = {C,S-l*C};
tree.update_eq(1,2,n,l+1,r,C);
lichao.update_eq(1,1,n,l,r,temp);
if (l>1) tree.update(1,2,n,l,calc(lichao.get(1,1,n,l),l) - calc(lichao.get(1,1,n,l-1),l-1));
if (r<n) tree.update(1,2,n,r+1,calc(lichao.get(1,1,n,r+1),r+1) - calc(lichao.get(1,1,n,r),r));
}
else
{
int l,r; cin>>l>>r;
node ans = tree.get(1,2,n,l+1,r);
cout<<ans.ans+1<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
114704 KB |
Output is correct |
| 2 |
Correct |
70 ms |
1060 KB |
Output is correct |
| 3 |
Correct |
88 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
70 ms |
1056 KB |
Output is correct |
| 5 |
Incorrect |
77 ms |
1092 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
329 ms |
114892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
914 ms |
114636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
329 ms |
114892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
114704 KB |
Output is correct |
| 2 |
Correct |
70 ms |
1060 KB |
Output is correct |
| 3 |
Correct |
88 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
70 ms |
1056 KB |
Output is correct |
| 5 |
Incorrect |
77 ms |
1092 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
