P1253 [yLOI2018] 扶苏的问题（洛谷）（线段树）

P1253 [yLOI2018] 扶苏的问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

要求实现3中操作
1、读入 v,将[l,r] 的数都变成v
2、将[l,r]的数都加上v
3、查询[l,r]中最大的数

#include <bits/stdc++.h>
#define x first
#define y second
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;typedef pair<int,int> PII;
typedef pair<char,int> PCI;
typedef long long LL;
typedef unsigned long long ULL;const int N=1e6+10 ;
const LL INF = 1e16;
int n,m;
int a[N];
struct tree{int l,r;LL v,add,x;// add->当前[l,r]要加的数 ,x->当前[l,r]全都要变成的数 
}tr[N*4];void pushup(int u)
{tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}// 先将u节点的区间的数都变成u要变的数，然后再加上要加上的数 
void pushdown(int u) 
{if(tr[u].x!=INF) // 当前u这个节点的区间有要变成的数 {tr[u<<1].add=tr[u<<1|1].add=0;// 大的区间的覆盖操作 优先于 子区间的 增加操作 tr[u<<1].v=tr[u<<1].x=tr[u].x; // 将值覆盖后 ，将标记往下传 tr[u<<1|1].v=tr[u<<1|1].x=tr[u].x;tr[u].x = INF;  // 修改完成 }if(tr[u].add){auto& v = tr[u].add;tr[u<<1].v+=v;tr[u<<1].add+=v;tr[u<<1|1].v+=v;tr[u<<1|1].add+=v;v=0;}}void build(int u,int l,int r)
{if(l == r ) {tr[u]={l,r,a[l],0,INF};}else {tr[u]={l,r,0,0,INF};int mid = l + r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int l,int r,LL v,int op)
{if(tr[u].l >= l && tr[u].r <=r ){if(op==1) // 将[l,r] 的每个数都修改为x {tr[u].v =tr[u].x=v;tr[u].add=0;return;}else // 将[l,r] 上的每个数都加上x {tr[u].v +=v;tr[u].add += v;return;}}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid ) modify(u<<1,l,r,v,op);if(r>mid) modify(u<<1|1,l,r,v,op);pushup(u);
}LL query(int u,int l,int r)
{if(tr[u].l >= l && tr[u].r <= r ) return tr[u].v;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL res = -INF;if(l <= mid ) res =max(res,query(u<<1,l,r));if(r > mid ) res = max(res,query(u<<1|1,l,r));return res;
}void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);int op;LL l,r,d;while(m-- ){cin>>op>>l>>r;if(op != 3){scanf("%lld",&d);modify(1,l,r,d,op);}else {printf("%lld\n",query(1,l,r));}}}int main()
{ios LL T=1;
//     cin>>T;while(T -- ){solve();}    return 0;
}