python/TangDou/AcWing/SegmentTree/Gorgeous/BZOJ4695_1.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;

//快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

#define ls u << 1
#define rs u << 1 | 1
const int N = 500010;
const int INF = 0x3f3f3f3f;

int n, m;

struct Node {
    int l, r;
    int mx, cx;  //最大值，最大值个数
    int sx;      //次大值
    int mi, ci;  //最小值，最小值个数
    int si;      //次小值
    LL sum;      //区间和
    LL tag;      // lazy tag,是不是有未消费掉的add修改标记
} tr[N << 2];

//向上推送统计信息，由左右儿子的统计信息更新父亲u的统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum; //区间和
    //更新最大值系列信息 mx,sx,cx
    if (tr[ls].mx == tr[rs].mx) {
        tr[u].mx = tr[ls].mx;
        tr[u].cx = tr[ls].cx + tr[rs].cx;
        tr[u].sx = max(tr[ls].sx, tr[rs].sx);
    } else if (tr[ls].mx > tr[rs].mx) {
        tr[u].mx = tr[ls].mx;
        tr[u].cx = tr[ls].cx;
        tr[u].sx = max(tr[ls].sx, tr[rs].mx);
    } else if (tr[ls].mx < tr[rs].mx) {
        tr[u].mx = tr[rs].mx;
        tr[u].cx = tr[rs].cx;
        tr[u].sx = max(tr[ls].mx, tr[rs].sx);
    }
    //更新最小值系列信息 mi,si,ci
    if (tr[ls].mi == tr[rs].mi) {
        tr[u].mi = tr[ls].mi;
        tr[u].si = min(tr[ls].si, tr[rs].si);
        tr[u].ci = tr[ls].ci + tr[rs].ci;
    } else if (tr[ls].mi > tr[rs].mi) {
        tr[u].mi = tr[rs].mi;
        tr[u].ci = tr[rs].ci;
        tr[u].si = min(tr[ls].mi, tr[rs].si);
    } else if (tr[ls].mi < tr[rs].mi) {
        tr[u].mi = tr[ls].mi;
        tr[u].ci = tr[ls].ci;
        tr[u].si = min(tr[ls].si, tr[rs].mi);
    }
}

//构建线段树
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].mx = tr[u].mi = tr[u].sum = read(); //最大值，最小值，区间和
        tr[u].cx = tr[u].ci = 1;                  //最大值个数=最小值个数=1
        tr[u].sx = -INF;                          //没有次大值
        tr[u].si = INF;                           //没有次小值
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
}

//将区间内所有数字更新为 max(a[i],v)
bool update_max(int u, int v) {
    //① 区间最小值都大于v,不需要进入区间
    if (tr[u].mi >= v) return true;

    //② 如果区间内数字都是一样的
    if (tr[u].mx == tr[u].mi) {
        tr[u].mx = tr[u].mi = v;
        tr[u].cx = tr[u].ci = tr[u].r - tr[u].l + 1;
        tr[u].sx = -INF, tr[u].si = INF;
        tr[u].sum = (LL)tr[u].cx * v;
        return true;
    }

    //③ 如果区间次小值大于v,只能更新最小值
    if (tr[u].si > v) {
        tr[u].sum += (LL)tr[u].ci * (v - tr[u].mi);
        tr[u].mi = v;
        tr[u].sx = max(tr[u].sx, v);
        tr[u].mx = max(tr[u].mx, v);
        return true;
    }

    //④ 以上情况都不是，那么讨论不清楚，只能是继续递归左右儿子，在子区间内尝试上面的三种情况更新
    return false;
}

//将区间内所有数字更新为 min(a[i],v)
bool update_min(int u, int v) {
    //① 区间最大值都小于v,不需要进入区间
    if (tr[u].mx <= v) return true;
    //② 如果区间内数字都是一样的
    if (tr[u].mx == tr[u].mi) {
        tr[u].mx = tr[u].mi = v;
        tr[u].cx = tr[u].ci = tr[u].r - tr[u].l + 1;
        tr[u].sx = -INF, tr[u].si = INF;
        tr[u].sum = (LL)tr[u].cx * v;
        return true;
    }
    //③ 如果区间次大值小于v,只能更新最大值
    if (tr[u].sx < v) {
        tr[u].sum -= (LL)tr[u].cx * (tr[u].mx - v);
        tr[u].mx = v;
        tr[u].si = min(tr[u].si, v);
        tr[u].mi = min(tr[u].mi, v);
        return true;
    }
    //④ 以上情况都不是，那么讨论不清楚，只能是继续递归左右儿子，在子区间内尝试上面的三种情况更新
    return false;
}

//整体命中时，区间每个数都要加上v,修改u节点的统计信息，并且传递tag懒标记
void update_add(int u, int v) {
    //① 最大值，最小值，次大值，次小值都会受到影响，都要加上v
    tr[u].mx += v, tr[u].mi += v, tr[u].sx += v, tr[u].si += v;
    //② 区间和也需要进行整体更新
    tr[u].sum += (LL)v * (tr[u].r - tr[u].l + 1); //为防止乘法受成的int溢出，需要先强制转换为LL
    //③ 区间加的tag懒标记需要标识在此区间上，并没有真的一路更新到叶子节点
    tr[u].tag += v;
}

//向下传递懒标记，一般是有新的更新操作，或者，有了查询操作时才这样做
void pushdown(int u) {
    if (tr[u].tag) { //如果区间加懒标记不为0，表示存在懒标记，需要通过update_add传递给左右儿子
        //主要的目标有两个：1、根据懒标记实时更新左右儿子的统计信息；2、左右儿子继承写上父亲的区间加懒标记
        update_add(ls, tr[u].tag), update_add(rs, tr[u].tag);
        //传递完毕，父节点区间加懒标记清零
        tr[u].tag = 0;
    }

    //其实本题的懒标记不只是区间加的tag,还有最大值tag和最小值tag,只不过没有显示的写出来

    //① 如果父亲的最大值标签信息，比左儿子的最大值小，这就是有问题，需要用tr[u].mx 对左儿子取min操作
    if (tr[ls].mx > tr[u].mx) update_min(ls, tr[u].mx);
    //② 如果父亲的最大值标签信息，比右儿子的最大值小，这就是有问题，需要用tr[u].mx 对右儿子取min操作
    if (tr[rs].mx > tr[u].mx) update_min(rs, tr[u].mx);

    //③ 如果父亲的最小值标签信息，比左儿子的最小值大，这就是有问题，需要用tr[u].mi 对左儿子取max操作
    if (tr[ls].mi < tr[u].mi) update_max(ls, tr[u].mi);
    //④ 如果父亲的最小值标签信息，比右儿子的最小值大，这就是有问题，需要用tr[u].mi 对右儿子取max操作
    if (tr[rs].mi < tr[u].mi) update_max(rs, tr[u].mi);
}

//区间加
void modify_add(int u, int l, int r, int v) {
    if (tr[u].l > r || tr[u].r < l) return; //无交集，直接返回
    if (tr[u].l >= l && tr[u].r <= r) {     //完全命中
        update_add(u, v);                   //更新统计信息+修改tag懒标记
        return;
    }
    //① 未完全命中，存在部分交集，先将以前的tag传递给左右儿子，再开始递归左右儿子
    pushdown(u);
    //② 分裂处理左右儿子
    modify_add(ls, l, r, v), modify_add(rs, l, r, v);
    //③ 因为子节点信息更新了，需要向上汇集统计信息
    pushup(u);
}

//更新最大值操作，拆分成了modify_max+update_max两个函数
void modify_max(int u, int l, int r, int v) {
    if (tr[u].l > r || tr[u].r < l) return; //无交集，直接返回
    if (l <= tr[u].l && tr[u].r <= r) //如果区间完整命中
        if (update_max(u, v)) return; //需要分类讨论，只有3种情况是可以进行更新的，其它情况只能继续分裂

    //分裂
    pushdown(u);
    modify_max(ls, l, r, v), modify_max(rs, l, r, v);
    pushup(u);
}

//更新最小值操作，拆分成了modify_min+update_min两个函数
void modify_min(int u, int l, int r, int v) {
    if (l > tr[u].r || r < tr[u].l) return;
    if (l <= tr[u].l && tr[u].r <= r)
        if (update_min(u, v)) return;

    pushdown(u);
    modify_min(ls, l, r, v), modify_min(rs, l, r, v);
    pushup(u);
}

//区间和
LL query_sum(int u, int l, int r) { //区间和注意用长整型
    if (tr[u].l > r || tr[u].r < l) return 0; //无交集，直接返回
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    return query_sum(ls, l, r) + query_sum(rs, l, r);
}

//区间最大值
int query_max(int u, int l, int r) {
    if (tr[u].l > r || tr[u].r < l) return -INF; //无交集，返回负无穷，保证结果不会从此区间获益
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mx;
    pushdown(u);
    return max(query_max(ls, l, r), query_max(rs, l, r));
}

//区间最小值
int query_min(int u, int l, int r) { //无交集，返回正无穷，保证结果不会从此区间获益
    if (tr[u].l > r || tr[u].r < l) return INF;
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].mi;
    pushdown(u);
    return min(query_min(ls, l, r), query_min(rs, l, r));
}

int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("BZOJ4695.in", "r", stdin);
#endif
    n = read();
    build(1, 1, n);

    m = read();
    while (m--) {
        int op = read(), l = read(), r = read(), x;
        if (op == 1) x = read(), modify_add(1, l, r, x);    //区间加
        if (op == 2) x = read(), modify_max(1, l, r, x);    //区间修改max运算
        if (op == 3) x = read(), modify_min(1, l, r, x);    //区间修改min运算
        if (op == 4) printf("%lld\n", query_sum(1, l, r));  //查询区间和
        if (op == 5) printf("%d\n", query_max(1, l, r));  //查询区间最大值
        if (op == 6) printf("%d\n", query_min(1, l, r));  //查询区间最小值
    }
    return 0;
}