【线段树/懒标】-【LG】P1253 扶苏的问题

\(\mathtt{TAGS}\)： 懒标线段树
\(\mathtt{ESTIMATION}\)：Tag * 2

题意

实现：

• 区间 \(\max\)
• 区间修改某个值
• 区间加

First. 确定数据结构

很显然，区间修改 + 区间查询所以——线段树。

Second. LazyTag

由于区间修改和区间加两个操作会互相干扰，所以对于每一个节点给两个 Tag，一个代表修改操作，一个代表加操作。

下文中，\(Tag1\) 为加，\(Tag2\) 为修改。

Third. 修改 And 加

递归进行，对于待修改区间，无论之前该区间加了多少次，修改都是直接覆盖，所以 \(Tag1\) 清空，\(Tag2 = x\)。

对于待加区间，先不管在此次操作之前的修改操作，直接修改区间值，并 \(Tag1 = Tag1 + x\)。

Fourth. 下放

由于不需要管每次修改操作之前的加操作，所以如果 \(Tag1 \ne 0\) 那么一定是在修改之后操作的，于是乎先下放修改操作，再下放加的操作。

注意
由于可能操作为修改区间中的数为 0，那么 Tag2 初值应该为一个不可能修改为的数，然后在 edit 函数判断是否有修改操作。

Code

#include <iostream>
using namespace std;
typedef long long ll;
#define inf (int)1e18
const int N = 1e6 + 10;
#define int ll
int n, m;
inline int max(int a, int b) {return a > b ? a : b;}
struct node {int l, r, val, tag1, tag2;}t[N * 4];
int a[N];
inline void build (int p, int l, int r) {
    if(l == r) t[p] = {l, r, a[l], 0, inf};
    else build(p * 2, l, (l + r) >> 1), build(p * 2 + 1, (l + r >> 1) + 1, r), t[p] = {l, r, max(t[p * 2].val, t[p * 2 + 1].val), 0, inf};
}
inline void add (int p, int k) {t[p].tag1 += k, t[p].val += k;}
inline void edit (int p, int k) {if(k == inf) return;t[p].tag2 = k, t[p].tag1 = 0, t[p].val = k;}
inline void pushdown (int p) {
    edit(p * 2, t[p].tag2), edit(p * 2 + 1, t[p].tag2);
    add (p * 2, t[p].tag1), add (p * 2 + 1, t[p].tag1);
    t[p].tag1 = 0, t[p].tag2 = inf;
}
inline void updata1 (int p, int l, int r, int k) {
    if(t[p].l > r || t[p].r < l) return;
    if(t[p].l >= l && t[p].r <= r) {add (p, k);return;}
    if(t[p].l < t[p].r) {
        pushdown(p);
        updata1 (p * 2, l, r, k), updata1(p * 2 + 1, l, r, k);
        t[p].val = max(t[p * 2].val, t[p * 2 + 1].val);
    }
}
inline void updata2 (int p, int l, int r, int k) {
    if(t[p].l > r || t[p].r < l) return;
    if(t[p].l >= l && t[p].r <= r) {edit(p, k); return;}
    if(t[p].l < t[p].r) {
        pushdown(p);
        updata2 (p * 2, l, r, k), updata2 (p * 2 + 1, l, r, k);
        t[p].val = max(t[p * 2].val, t[p * 2 + 1].val); 
    }
}
inline ll getmax (int p, int l, int r) {
    if(t[p].l > r || t[p].r < l) return -inf;
    if(t[p].l >= l && t[p].r <= r) return t[p].val;
    pushdown(p);
    return max(getmax(p * 2, l, r), getmax(p * 2 + 1, l, r));
}
const int bufsize = 220005;
char gtchar(){
    static char buf[bufsize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufsize, stdin), p1 == p2)? EOF: *p1++;
}
ll read(){
	ll ret = 0;
	char ch = gtchar();
	bool f = false;
	while(ch < '0' || ch > '9') f |= ch == '-', ch = gtchar();
	while(ch >= '0' && ch <= '9') ret = ret * 10 + (ch ^ 48), ch = gtchar();
	return f? -ret: ret;
}
int opt, l, r, x;

signed main() {
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    n = read(), m = read();
    for (int i = 1; i <= n; i = -~i) a[i] = read();
    build(1, 1, n);
    while(m --) {
        opt = read(), l = read(), r = read();
        if(opt == 1) x = read(), updata2 (1, l, r, x);
        else if(opt == 2) x = read(), updata1 (1, l, r, x);
        else printf("%lld\n", getmax(1, l, r));
    }
    return 0;
}