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

     tag值存两个，一个覆盖值，一个累加值，再开一个变量存是否有覆盖值。因为覆盖值可能为零，也可以置为一个极小的值作为覆盖值是否存在的判断条件（如-1e18），除了注释的部分要注意一下以外，其余纯模板。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define int long long
typedef pair<int, int> PII;
int n, m, k;
int T;
int a[N];
int tree[N * 4];
struct node
{int x, y, z;          //分别指的是覆盖值，累加值和是否有覆盖值。只需要维护覆盖值，不需要维护累加值
} tag[N * 4];
void push_up(int rt)
{tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}void build(int rt, int l, int r)
{if (l == r){tree[rt] = a[l];return;}int mid = l + r >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);push_up(rt);
}void push_down(int rt)
{if(tag[rt].z)       //如果有覆盖值{tag[rt<<1].x = tag[rt].x, tag[rt<<1|1].x = tag[rt].x;tag[rt<<1].y = tag[rt].y, tag[rt<<1|1].y = tag[rt].y; //特别注意这里的累加值要直接赋值过去，而不是+=tag[rt<<1].z = tag[rt<<1|1].z = 1;                   //因为若存在覆盖值，之前存在的累加值就已经没有意义tree[rt<<1] = tag[rt].x + tag[rt].y;tree[rt<<1|1] = tag[rt].x + tag[rt].y;}else{tag[rt<<1].y += tag[rt].y;tag[rt<<1|1].y += tag[rt].y;tree[rt<<1] += tag[rt].y;tree[rt<<1|1] += tag[rt].y;}tag[rt].x = tag[rt].y = tag[rt].z = 0;
}void updata(int rt, int l, int r, int start, int end, int data, int f)
{if(f==1){if(start <= l && end >= r){tag[rt].x = data;tag[rt].y = 0;        //累加值置为0，都被覆盖了，已经没有意义tree[rt] = data;tag[rt].z = 1;        //存在覆盖值（覆盖值可以是零，所以不能用tag[i].x==0作为判断条件）return;}}else{if(start <= l && end >= r){tree[rt] += data;tag[rt].y += data;return;}}push_down(rt);int mid = l + r >> 1;if(start <= mid) updata(rt<<1, l, mid, start, end, data, f);if(end >= mid + 1) updata(rt<<1|1, mid+1, r, start, end, data, f);push_up(rt); 
}int query(int rt, int l, int r, int start, int end)
{if(start <= l && end >= r)return tree[rt];push_down(rt);int res = -1e18;          //因为会爆int，一定要非常小，没注意到，写的0x3f3f3f3f卡好久int mid = l + r >> 1;if(start <= mid) res = max(res, query(rt<<1, l, mid, start, end));if(end >= mid+1) res = max(res, query(rt<<1|1, mid+1, r, start, end));return res;
}signed main()
{ios::sync_with_stdio(false), cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}build(1, 1, n);while (m--){int a, b, c, d;cin >> k;if (k == 1){cin >> a >> b >> c;updata(1, 1, n, a, b, c, 1);}else if (k == 2){cin >> a >> b >> c;updata(1, 1, n, a, b, c, 2);}else{cin >> a >> b;int t = query(1, 1, n, a, b);cout << t << "\n";}}return 0;
}