吉司机线段树--区间最值操作

区间最值操作

给定一个长度为 N序列，编号从1 到 N。要求支持下面几种操作：
1.给一个区间[L,R] 加上一个数x
2.把一个区间[L,R] 里小于x 的数变成x
3.把一个区间[L,R] 里大于x 的数变成x
4.求区间[L,R] 的和
5.求区间[L,R] 的最大值
6.求区间[L,R] 的最小值

最假女选手

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
template<class...Args>
void debug(Args... args) {//Parameter pack
    auto tmp = { (cout << args << ' ', 0)... };
    cout << "\n";
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pll;
typedef pair<int, int>pii;
const ll N = 1e6 + 5;
const ll MOD = 998244353;
const ll INF = 1e9 + 7;

struct node {
    int maxv, next_max, cnt_max;//最大值 次大值  最大值个数
    int minv, next_min, cnt_min;//最小值 次小值  最小值个数
    int add;//加法懒标记
    ll sum;//区间和
}tree[N << 2];
int w[N];
void push_up(int root) {
    //更新和
    tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
    //更新最大值及其附加属性
    if (tree[root << 1].maxv == tree[root << 1 | 1].maxv) {//如果左子树的最大值等于右子树的最大值
        tree[root].maxv = tree[root << 1].maxv;//将根节点的最大值更新
        tree[root].cnt_max = tree[root << 1].cnt_max + tree[root << 1 | 1].cnt_max;//根节点最大值的数量为左右子树最大值的个数和
        tree[root].next_max = max(tree[root << 1].next_max, tree[root << 1 | 1].next_max);//根节点的次大值为左右子树次大值的最大的那个
    }
    else if (tree[root << 1].maxv > tree[root << 1 | 1].maxv) {//如果左子树的最大值大于右子树的最大值
        tree[root].maxv = tree[root << 1].maxv;//根节点的最大值左子树的最大值
        tree[root].cnt_max = tree[root << 1].cnt_max;//根节点的最大值数量为左子树最大值的数量
        tree[root].next_max = max(tree[root << 1].next_max, tree[root << 1 | 1].maxv);//根节点的次大值为左子树次大值和右子树最大值的较大者
    }
    else {//如果右子树的最大值大于左子树的最大值
        tree[root].maxv = tree[root << 1 | 1].maxv;
        tree[root].cnt_max = tree[root << 1 | 1].cnt_max;
        tree[root].next_max = max(tree[root << 1 | 1].next_max, tree[root << 1].maxv);
    }
    //更新最小值及其附加属性
    if (tree[root << 1].minv == tree[root << 1 | 1].minv) {//如果左子树的最小值等于右子树的最小值
        tree[root].minv = tree[root << 1].minv;//将根节点的最大值更新
        tree[root].cnt_min = tree[root << 1].cnt_min + tree[root << 1 | 1].cnt_min;//根节点最小值的数量为左右子树最小值的个数和
        tree[root].next_min = min(tree[root << 1].next_min, tree[root << 1 | 1].next_min);//根节点的次小值为左右子树次小值的最小的那个
    }
    else if (tree[root << 1].minv < tree[root << 1 | 1].minv) {//如果左子树的最小值小于右子树的最小值
        tree[root].minv = tree[root << 1].minv;//根节点的最小值左子树的最小值
        tree[root].cnt_min = tree[root << 1].cnt_min;//根节点的最小值数量为左子树最小值的数量
        tree[root].next_min = min(tree[root << 1].next_min, tree[root << 1 | 1].minv);//根节点的次小值为左子树次小值和右子树最小值的较小者
    }
    else {//如果右子树的最小值小于左子树的最小值
        tree[root].minv = tree[root << 1 | 1].minv;
        tree[root].cnt_min = tree[root << 1 | 1].cnt_min;
        tree[root].next_min = min(tree[root << 1 | 1].next_min, tree[root << 1].minv);
    }
}
void build(int root, int l, int r) {
    if (l == r) {
        tree[root].sum = tree[root].maxv = tree[root].minv = w[l];
        tree[root].cnt_max = tree[root].cnt_min = 1;
        tree[root].next_max = -INF;
        tree[root].next_min = INF;
        return;
    }
    int mid = (l + r) >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    push_up(root);
}
void update_add(int root, int l, int r, int k) {//下放加法懒标记节点各属性的变化
    tree[root].add += k;
    tree[root].sum = tree[root].sum + k * (r - l + 1ll);
    tree[root].maxv += k;
    tree[root].next_max += k;
    tree[root].minv += k;
    tree[root].next_min += k;
}
void update_min(int root, int k) {//对区间求min()后节点对应的各属性的变化,在此之前有判断该节点是否要取min()
    tree[root].sum = tree[root].sum - 1ll * (tree[root].maxv - k) * tree[root].cnt_max;
    if (tree[root].maxv == tree[root].minv)tree[root].maxv = tree[root].minv = k;
    else if (tree[root].maxv == tree[root].next_min)tree[root].maxv = tree[root].next_min = k;
    else tree[root].maxv = k;
}
void update_max(int root, int k) {//对区间求max()后节点对应的各属性的变化,再次之前有判断该节点是否要取max()
    tree[root].sum = tree[root].sum + 1ll * (k - tree[root].minv) * tree[root].cnt_min;
    if (tree[root].minv == tree[root].maxv)tree[root].minv = tree[root].maxv = k;
    else if (tree[root].minv == tree[root].next_max)tree[root].minv = tree[root].next_max = k;
    else tree[root].minv = k;
}
void push_down(int root, int l, int r) {
    int mid = (l + r) >> 1;
    if (tree[root].add) {//下放加法懒标记
        update_add(root << 1, l, mid, tree[root].add);
        update_add(root << 1 | 1, mid + 1, r, tree[root].add);
        tree[root].add = 0;
    }
   //下放根节点的加法的懒标记后再维护左右子树信息
    if (tree[root].maxv < tree[root << 1].maxv)update_min(root << 1, tree[root].maxv);
    if (tree[root].maxv < tree[root << 1 | 1].maxv)update_min(root << 1 | 1, tree[root].maxv);

    if (tree[root].minv > tree[root << 1].minv)update_max(root << 1, tree[root].minv);
    if (tree[root].minv > tree[root << 1 | 1].minv)update_max(root << 1 | 1, tree[root].minv);
}
void modify_add(int root, int L, int R, int l, int r, int k) {//将区间加上某个数
    if (l == L && r == R) {
        update_add(root, l, r, k);
        return;
    }
    push_down(root, L, R);
    int MID = (L + R) >> 1;
    if (r <= MID)modify_add(root << 1, L, MID, l, r, k);
    else if (l > MID)modify_add(root << 1 | 1, MID + 1, R, l, r, k);
    else modify_add(root << 1, L, MID, l, MID, k), modify_add(root << 1 | 1, MID + 1, R, MID + 1, r, k);
    push_up(root);
}
void modify_min(int root, int L, int R, int l, int r, int k) {//对区间求min()
    if (k >= tree[root].maxv)return;
    if (l == L && r == R && k > tree[root].next_max) {
        update_min(root, k);
        return;
    }
    push_down(root, L, R);
    int MID = (L + R) >> 1;
    if (r <= MID)modify_min(root << 1, L, MID, l, r, k);
    else if (l > MID)modify_min(root << 1 | 1, MID + 1, R, l, r, k);
    else modify_min(root << 1, L, MID, l, MID, k), modify_min(root << 1 | 1, MID + 1, R, MID + 1, r, k);
    push_up(root);
}
void modify_max(int root, int L, int R, int l, int r, int k) {//对区间求max()
    if (k <= tree[root].minv)return;
    if (l == L && r == R && k < tree[root].next_min) {
        update_max(root, k);
        return;
    }
    push_down(root, L, R);
    int MID = (L + R) >> 1;
    if (r <= MID)modify_max(root << 1, L, MID, l, r, k);
    else if (l > MID)modify_max(root << 1 | 1, MID + 1, R, l, r, k);
    else modify_max(root << 1, L, MID, l, MID, k), modify_max(root << 1 | 1, MID + 1, R, MID + 1, r, k);
    push_up(root);
}
ll query_sum(int root, int L, int R, int l, int r) {//询问区间的和
    if (l == L && r == R)return tree[root].sum;
    push_down(root, L, R);
    int MID = (L + R) >> 1;
    if (r <= MID)return query_sum(root << 1, L, MID, l, r);
    else if (l > MID)return query_sum(root << 1 | 1, MID + 1, R, l, r);
    else return query_sum(root << 1, L, MID, l, MID) + query_sum(root << 1 | 1, MID + 1, R, MID + 1, r);

}
int query_max(int root, int L, int R, int l, int r) {//询问区间的最大值
    if (l == L && r == R)return tree[root].maxv;
    push_down(root, L, R);
    int MID = (L + R) >> 1;
    if (r <= MID)return query_max(root << 1, L, MID, l, r);
    else if (l > MID)return query_max(root << 1 | 1, MID + 1, R, l, r);
    else return max(query_max(root << 1, L, MID, l, MID), query_max(root << 1 | 1, MID + 1, R, MID + 1, r));
}
int query_min(int root, int L, int R, int l, int r) {//询问区间的最小值
    if (l == L && r == R)return tree[root].minv;
    push_down(root, L, R);
    int MID = (L + R) >> 1;
    if (r <= MID)return query_min(root << 1, L, MID, l, r);
    else if (l > MID)return query_min(root << 1 | 1, MID + 1, R, l, r);
    else return min(query_min(root << 1, L, MID, l, MID), query_min(root << 1 | 1, MID + 1, R, MID + 1, r));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> w[i];
    build(1, 1, n);

    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int opt, l, r;
        cin >> opt >> l >> r;
        int x;
        if (opt == 1) cin >> x, modify_add(1, 1, n, l, r, x);
        if (opt == 2) cin >> x, modify_max(1, 1, n, l, r, x);
        if (opt == 3) cin >> x, modify_min(1, 1, n, l, r, x);
        if (opt == 4) cout << query_sum(1, 1, n, l, r) << "\n";
        if (opt == 5) cout << query_max(1, 1, n, l, r) << "\n";
        if (opt == 6) cout << query_min(1, 1, n, l, r) << "\n";
    }

    return 0;
}