LuoguP1253 扶苏的问题

线段树。

Sol.

实际上相当于维护一颗线段树，支持区间覆盖、区间加和区间查询最大值。

维护最大值很好办，区间覆盖和区间加我们怎么维护呢？

首先，区间覆盖和区间加一定都分别需要记一个懒标记。我们把区间覆盖的懒标记记为 \(ctag\)，区间加的懒标记记为 \(atag\)，那么我们如何把标记 \(\text{pushdown}\) 呢？

首先，初始化要选择一个尽量不影响之后操作的值。\(atag\) 显然选择 \(0\) 即可。由于要更改的数字有正有负，\(ctag\) 可以选取 \(-\infty\)，在程序中我选用了 \(1e18+7\) 作为 \(\text{INF}\)。

考虑到如果我们当前节点有一个 \(atag\) 标记，之后又打上了一个 \(ctag\) 标记，那么要覆盖的值会直接把要加的值覆盖，也就是说 \(ctag\) 会直接清除 \(atag\)。而如果先打上 \(ctag\)，再打上 \(atag\)，则需要先把 \(ctag\) 下放，再下放 \(atag\)。那么我们的 \(\text{pushdown}\) 可以这么写：

void af(int k, int v) //把下放的操作封装一下可以使代码更简洁
{
    t[k].maxx += v;
    t[k].atag += v;
}

void cf(int k, int v)
{
    t[k].maxx = v;
    t[k].ctag = v;
}

void cpushdown(int k) //ctag 的下放
{
    if(t[k].ctag == -INF) return; //如果没有标记，返回
    t[ls].atag = t[rs].atag = 0; //抹除 atag
    cf(ls, t[k].ctag), cf(rs, t[k].ctag); //ctag 下放
    t[k].ctag = -INF; //当前节点 ctag 清零
}

void apushdown(int k) //atag 的下放
{
    if(t[k].atag == 0) return; //如果没有标记，返回
    cpushdown(k); //先把 ctag 下放
    af(ls, t[k].atag), af(rs, t[k].atag); //atag 下放
    t[k].atag = 0; //当前节点 atag 清零
}

void pushdown(int k) 
{
    cpushdown(k);
    apushdown(k);
}
//一次 pushdown 操作包括 ctag 的下放和 atag 的下放，都要进行

那么操作呢？区间加操作和之前一样即可，区间覆盖操作需要清除当前节点的 \(atag\)。

其他部分即为普通线段树模板。

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long 

const int MAXN = 1e6 + 7;
const int INF = 1e18 + 7;

#define ls (k << 1)
#define rs (k << 1 | 1)

inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * f;
}

struct Tree
{
    int maxx;
    int l, r;
    int atag, ctag;
}t[MAXN << 2];

int a[MAXN];

int n, q;

void pushup(int k)
{
    t[k].maxx = max(t[ls].maxx, t[rs].maxx);
}

void af(int k, int v)
{
    t[k].maxx += v;
    t[k].atag += v;
}

void cf(int k, int v)
{
    t[k].maxx = v;
    t[k].ctag = v;
}

void cpushdown(int k)
{
    if(t[k].ctag == -INF) return;
    t[ls].atag = t[rs].atag = 0;
    cf(ls, t[k].ctag), cf(rs, t[k].ctag);
    t[k].ctag = -INF;
}

void apushdown(int k)
{
    if(t[k].atag == 0) return;
    cpushdown(k);
    af(ls, t[k].atag), af(rs, t[k].atag);
    t[k].atag = 0;
}

void pushdown(int k)
{
    cpushdown(k);
    apushdown(k);
}

void build(int k, int l, int r)
{
    t[k].l = l;
    t[k].r = r;
    t[k].atag = 0;
    t[k].ctag = -INF;
    if(l == r)
    {
        t[k].maxx = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(k);
}

void update(int k, int l, int r, int v)
{
    if(l <= t[k].l && t[k].r <= r)
    {
        af(k, v);
        return;
    }
    pushdown(k);
    int mid = (t[k].l + t[k].r) >> 1;
    if(l <= mid) update(ls, l, r, v);
    if(r > mid) update(rs, l, r, v);
    pushup(k);
}

void cover(int k, int l, int r, int v)
{
    if(l <= t[k].l && t[k].r <= r)
    {
        t[k].atag = 0;
        cf(k, v);
        return;
    }
    pushdown(k);
    int mid = (t[k].l + t[k].r) >> 1;
    if(l <= mid) cover(ls, l, r, v);
    if(r > mid) cover(rs, l, r, v);
    pushup(k);
}

int query(int k, int l, int r)
{
    int res = -INF;
    if(l <= t[k].l && t[k].r <= r) return t[k].maxx;
    pushdown(k);
    int mid = (t[k].l + t[k].r) >> 1;
    if(l <= mid) res = max(res, query(ls, l, r));
    if(r > mid) res = max(res, query(rs, l, r));
    return res;
}

signed main()
{
    n = read(), q = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    build(1, 1, n);
    while(q--)
    {
        int opt = read();
        if(opt == 1)
        {
            int l = read(), r = read(), x = read();
            cover(1, l, r, x);
        }
        if(opt == 2)
        {
            int l = read(), r = read(), x = read();
            update(1, l, r, x);
        }
        if(opt == 3)
        {
            int l = read(), r = read();
            printf("%lld\n", query(1, l, r));
        }
    }
    return 0;
}