20分呜呜
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
struct node{
int l,r;
bool f;
// int z;
ll add;
ll val;
}tree[4000000];
int a[1000001];
int op,l,r,x;
int n,q;
void pushup(int id){
tree[id].val=max(tree[ls(id)].val,tree[rs(id)].val);
}
void pushdown(int id){
if(tree[id].f){
tree[id].f=0;
tree[ls(id)].f=tree[rs(id)].f=1;
tree[ls(id)].val=tree[rs(id)].val=tree[id].val;
tree[ls(id)].add=tree[rs(id)].add=tree[id].add=0;
}
else{
tree[ls(id)].add+=tree[id].add;
tree[rs(id)].add+=tree[id].add;
tree[ls(id)].val+=tree[id].add;
tree[rs(id)].val+=tree[id].add;
tree[id].add=0;
}
}
void build(int id,int l,int r){
// cout<<id<<": "<<l<<"~~"<<r<<endl;
tree[id].l=l;
tree[id].r=r;
tree[id].add=tree[id].val=tree[id].f=0;
if(l==r){
tree[id].val=a[l];
return ;
}
int mid=l+r>>1;
build(ls(id),l,mid);
build(rs(id),mid+1,r);
pushup(id);
}
void upd(int id,int l,int r,int x,int op){
// cout<<id<<": "<<tree[id].l<<"--"<<tree[id].r<<endl;
if(l<=tree[id].l&&tree[id].r<=r){
if(op==1){
tree[id].f=1;
tree[id].add=0;
tree[id].val=x;
}
else{
if(!tree[id].f)tree[id].add+=x;
tree[id].val+=x;
}
return ;
}
pushdown(id);
int mid=tree[id].l+tree[id].r>>1;
if(l<=mid)upd(ls(id),l,r,x,op);
if(r>mid)upd(rs(id),l,r,x,op);
pushup(id);
}
ll query(int id,int l,int r){
if(l<=tree[id].l&&tree[id].r<=r){
return tree[id].val;
}
pushdown(id);
int mid=tree[id].l+tree[id].r>>1;
ll ans=-1e18;
if(l<=mid)ans=max(ans,query(ls(id),l,mid));
if(r>mid)ans=max(ans,query(rs(id),mid+1,r));
return ans;
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
while(q--){
scanf("%d%d%d",&op,&l,&r);
if(op==3){
printf("%lld\n",query(1,l,r));
}
else{
scanf("%d",&x);
upd(1,l,r,x,op);
}
}
return 0;
}
```
by WsW_ @ 2023-08-14 22:28:21
巨佬%%%
by ncwzdlsd @ 2023-08-14 22:41:22
@[AC_love](/user/186472) 大佬教我线段树优化 DP 吧/bx/bx
by ncwzdlsd @ 2023-08-14 22:41:48
@[AC_love](/user/186472) 不一定非得用 `scanf`，你把同步流关了捆绑关了也能过吧
by ncwzdlsd @ 2023-08-14 22:42:24
@[ncwzdlsd](/user/822239)
```
关同步流的 cin 和 cout 速度比 printf 和 scanf 确实可能快很多，但是当你换了 printf 和 scanf 的时候，你的代码复杂度的瓶颈就已经不在输入输出上了，所以这个关闭同步流其实我觉得意义不大，而且有时候关闭同步流却不小心把两种输入输出混用还会导致挂掉，这样就很难办
```
by AC_love @ 2023-08-14 22:47:07
@[WsW_](/user/349824) 你在每个函数里加点输出当前节点维护权值还有更新什么的语句自己调一调看看吧，我自己的代码调了两个小时才调出来，刚才我给你看了几遍感觉逻辑上没毛病，应该是细节出问题了，你输出一下中间变量试试看
比如这样：
```cpp
#include <bits/stdc++.h>
#define int long long
#define tpl t[p].l
#define tpr t[p].r
#define t2pl t[p*2].l
#define t2pr t[p*2].r
#define t2p1l t[p*2+1].l
#define t2p1r t[p*2+1].r
#define tpa t[p].add
#define tpm t[p].m
#define tpc t[p].changement
#define t2pm t[p*2].m
#define t2p1m t[p*2+1].m
#define t2pc t[p*2].changement
#define t2p1c t[p*2+1].changement
#define t2pa t[p*2].add
#define t2p1a t[p*2+1].add
#define mn -214748364700000
using namespace std;
int a[1919810];
struct tree
{
int l;
int r;
int add;
int changement;
int m;
};
tree t[8114514];
void build(int p, int l, int r)
{
tpl = l;
tpr = r;
tpc = mn;
if(l == r)
{
tpm = a[l];
tpc = mn;
// cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
return;
}
int mid = (l + r) / 2;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
tpm = max(t2pm, t2p1m);
// cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
return;
}
void spreadc(int p)
{
if(tpc != mn)
{
// cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，更改为了" << tpc << "\n";
// tpm = tpc;
t2pm = tpc;
t2p1m = tpc;
t2pc = tpc;
t2p1c = tpc;
t2pa = 0;
t2p1a = 0;
// tpa = 0;
// cout << 2*p << "号节点维护的范围为从" << t2pl << "到" << t2pr << "，更改为了" << tpc << "\n";
// cout << 2*p+1 << "号节点维护的范围为从" << t2p1l << "到" << t2p1r << "，更改为了" << tpc << "\n";
tpc = mn;
}
}
void spreada(int p)
{
if(tpa != 0)
{
t2pm += tpa;
t2p1m += tpa;
t2pa += tpa;
t2p1a += tpa;
// cout << 2*p << "号节点维护的范围为从" << t2pl << "到" << t2pr << "，更改了" << tpa << "\n";
// cout << 2*p+1 << "号节点维护的范围为从" << t2p1l << "到" << t2p1r << "，更改了" << tpa << "\n";
tpa = 0;
}
}
void pushdown(int p)
{
spreadc(p);
spreada(p);
}
void changec(int p, int l, int r, int k)
{
if(l <= tpl && tpr <= r)
{
// cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，更改为了" << k << "\n";
tpm = k;
tpa = 0;
tpc = k;
return;
}
pushdown(p);
int mid = (tpl + tpr) / 2;
if(l <= mid)
changec(p * 2, l, r, k);
if(r > mid)
changec(p * 2 + 1, l, r, k);
tpm = max(t2pm, t2p1m);
}
void changea(int p, int l, int r, int k)
{
pushdown(p);
if(l <= tpl && tpr <= r)
{
// cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，更改了" << k << "\n";
tpm += k;
tpa += k;
return;
}
pushdown(p);
int mid = (tpl + tpr) / 2;
if(l <= mid)
changea(p * 2, l, r, k);
if(r > mid)
changea(p * 2 + 1, l, r, k);
tpm = max(t2pm, t2p1m);
}
int ask(int p, int l, int r)
{
if(l <= tpl && tpr <= r)
{
// cout << p << "号节点在区间范围内，维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
return tpm;
}
pushdown(p);
int mid = (tpl + tpr) / 2;
// cout << mid << "??????" << l << " " << r << "\n";
int maxn = mn;
if(l <= mid)
{
// cout << 2 * p << "号节点部分在区间范围内，维护的范围为从" << t2pl << "到" << t2pr << "\n";
maxn = max(maxn, ask(p * 2, l, r));
}
if(r > mid)
{
// cout << 2 * p + 1 << "号节点部分在区间范围内，维护的范围为从" << t2p1l << "到" << t2p1r << "\n";
maxn = max(maxn, ask(p * 2 + 1, l, r));
}
return maxn;
}
//void print(int p)
//{
// cout << p << "号节点维护的范围为从" << tpl << "到" << tpr << "，最大值为" << tpm << "\n";
//
// if(tpl == tpr)
// return;
//
// print(p * 2);
// print(p * 2 + 1);
//}
int n, m;
signed main()
{
// freopen("a.txt", "r", stdin);
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i = i + 1)
scanf("%lld", &a[i]);
build(1, 1, n);
for(int i = 1; i <= m; i = i + 1)
{
int op, l, r, x;
scanf("%lld%lld%lld", &op, &l, &r);
if(op == 1)
{
scanf("%lld", &x);
changec(1, l, r, x);
}
if(op == 2)
{
scanf("%lld", &x);
changea(1, l, r, x);
}
if(op == 3)
printf("%lld\n", ask(1, l, r));
// cout << "\n\n\n";
//
// print(1);
// cout << "\n\n\n";
}
return 0;
}
```
by AC_love @ 2023-08-14 22:56:24
@[AC_love](/user/186472) %%%
by JT_dw_ @ 2023-08-14 23:12:28
加前的覆盖注意不要下放到叶子节点，这就是为什么八倍空间才能过。
```cpp
if(tr[u].l!=tr[u].r) pushdown2(u);
```
by Falling_Sakura @ 2023-08-15 20:52:15
%%% 栽在了inf上
by Enoch006 @ 2023-08-24 18:36:00