解题步骤

这道题要求我们处理一个序列的多种区间操作，包括区间加、区间取下界、区间取上界以及区间查询（和、最大值、最小值）。由于数据范围较大（n, m ≤ 5×10^5），必须使用高效的数据结构，这里选择带懒惰标记的线段树，通过合理设计标记和操作逻辑来实现高效更新和查询。

核心思路

1. 线段树节点设计：每个节点需存储区间和（sum）、最大值（max_val）、最小值（min_val），以及三种懒惰标记：

   • add：区间加法标记（初始为0）。
   • set_low：区间下界标记（将小于x的数改为x，初始为-∞表示无效）。
   • set_high：区间上界标记（将大于x的数改为x，初始为+∞表示无效）。

2. 标记处理逻辑：

   • 加法标记（add）：对区间内所有元素加x，会影响sum、max_val、min_val，且需与其他标记协同处理。
   • 下界标记（set_low）：确保区间内元素不小于x，需基于当前add转换为原始值的下界。
   • 上界标记（set_high）：确保区间内元素不大于x，需基于当前add转换为原始值的上界。

3. 标记下放（push_down）：当节点有子节点时，需将当前节点的标记传递给子节点，确保子节点状态正确后再处理子节点。

4. 操作实现：

   • 对于更新操作（加、取下界、取上界），通过递归遍历线段树，在合适的节点应用标记并更新状态。
   • 对于查询操作（和、最大值、最小值），递归遍历线段树，合并子节点结果返回。

代码实现

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

typedef long long ll;
const int MAXN = 5e5 + 10;
const ll INF = 1e18;
const ll NEG_INF = -1e18;

struct Node {
    int l, r;
    ll sum;
    ll max_val, min_val;
    ll add;         // 加法标记
    ll set_low;     // 原始值下界（实际值 = 原始值 + add ≥ set_low + add）
    ll set_high;    // 原始值上界（实际值 = 原始值 + add ≤ set_high + add）
} tree[4 * MAXN];

int a[MAXN];
int n, m;

// 计算原始值的有效范围 [L, H]
void calc_range(const Node &node, ll &L, ll &H) {
    ll orig_min = node.min_val - node.add;  // 原始值的最小值
    ll orig_max = node.max_val - node.add;  // 原始值的最大值
    L = max(orig_min, node.set_low);
    H = min(orig_max, node.set_high);
}

// 推送标记到子节点
void push_down(int u) {
    int mid = (tree[u].l + tree[u].r) >> 1;
    int left = u << 1, right = u << 1 | 1;

    // 处理加法标记
    if (tree[u].add != 0) {
        // 更新左子节点
        tree[left].add += tree[u].add;
        tree[left].sum += tree[u].add * (mid - tree[left].l + 1);
        tree[left].max_val += tree[u].add;
        tree[left].min_val += tree[u].add;

        // 更新右子节点
        tree[right].add += tree[u].add;
        tree[right].sum += tree[u].add * (tree[right].r - mid);
        tree[right].max_val += tree[u].add;
        tree[right].min_val += tree[u].add;

        // 清除当前节点加法标记
        tree[u].add = 0;
    }

    // 处理下界标记
    if (tree[u].set_low != NEG_INF) {
        // 更新左子节点
        tree[left].set_low = max(tree[left].set_low, tree[u].set_low);
        ll L, H;
        calc_range(tree[left], L, H);
        tree[left].max_val = H + tree[left].add;
        tree[left].min_val = L + tree[left].add;
        if (L == H) {
            tree[left].sum = (L + tree[left].add) * (mid - tree[left].l + 1);
        }

        // 更新右子节点
        tree[right].set_low = max(tree[right].set_low, tree[u].set_low);
        calc_range(tree[right], L, H);
        tree[right].max_val = H + tree[right].add;
        tree[right].min_val = L + tree[right].add;
        if (L == H) {
            tree[right].sum = (L + tree[right].add) * (tree[right].r - mid);
        }

        // 清除当前节点下界标记
        tree[u].set_low = NEG_INF;
    }

    // 处理上界标记
    if (tree[u].set_high != INF) {
        // 更新左子节点
        tree[left].set_high = min(tree[left].set_high, tree[u].set_high);
        ll L, H;
        calc_range(tree[left], L, H);
        tree[left].max_val = H + tree[left].add;
        tree[left].min_val = L + tree[left].add;
        if (L == H) {
            tree[left].sum = (L + tree[left].add) * (mid - tree[left].l + 1);
        }

        // 更新右子节点
        tree[right].set_high = min(tree[right].set_high, tree[u].set_high);
        calc_range(tree[right], L, H);
        tree[right].max_val = H + tree[right].add;
        tree[right].min_val = L + tree[right].add;
        if (L == H) {
            tree[right].sum = (L + tree[right].add) * (tree[right].r - mid);
        }

        // 清除当前节点上界标记
        tree[u].set_high = INF;
    }
}

// 构建线段树
void build(int u, int l, int r) {
    tree[u].l = l;
    tree[u].r = r;
    tree[u].add = 0;
    tree[u].set_low = NEG_INF;
    tree[u].set_high = INF;
    if (l == r) {
        tree[u].sum = a[l];
        tree[u].max_val = a[l];
        tree[u].min_val = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
    tree[u].max_val = max(tree[u << 1].max_val, tree[u << 1 | 1].max_val);
    tree[u].min_val = min(tree[u << 1].min_val, tree[u << 1 | 1].min_val);
}

// 区间加x
void update_add(int u, int l, int r, ll x) {
    if (tree[u].l >= l && tree[u].r <= r) {
        tree[u].add += x;
        tree[u].sum += x * (tree[u].r - tree[u].l + 1);
        tree[u].max_val += x;
        tree[u].min_val += x;
        return;
    }
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    if (l <= mid) update_add(u << 1, l, r, x);
    if (r > mid) update_add(u << 1 | 1, l, r, x);
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
    tree[u].max_val = max(tree[u << 1].max_val, tree[u << 1 | 1].max_val);
    tree[u].min_val = min(tree[u << 1].min_val, tree[u << 1 | 1].min_val);
}

// 区间取下界（小于x的变为x）
void update_setmin(int u, int l, int r, ll x) {
    if (tree[u].l >= l && tree[u].r <= r) {
        // 实际值 >= x → 原始值 >= x - add
        ll target = x - tree[u].add;
        ll L, H;
        calc_range(tree[u], L, H);
        if (L >= target) return;  // 已满足，无需更新
        if (H < target) {         // 整个区间都需更新为target
            tree[u].set_low = max(tree[u].set_low, target);
            tree[u].min_val = x;
            tree[u].max_val = x;
            tree[u].sum = x * (tree[u].r - tree[u].l + 1);
            return;
        }
        // 部分更新，需修改标记并更新状态
        tree[u].set_low = max(tree[u].set_low, target);
        L = max(L, target);
        tree[u].min_val = L + tree[u].add;
        // sum无法直接计算，需后续push_down处理
        return;
    }
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    if (l <= mid) update_setmin(u << 1, l, r, x);
    if (r > mid) update_setmin(u << 1 | 1, l, r, x);
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
    tree[u].max_val = max(tree[u << 1].max_val, tree[u << 1 | 1].max_val);
    tree[u].min_val = min(tree[u << 1].min_val, tree[u << 1 | 1].min_val);
}

// 区间取上界（大于x的变为x）
void update_setmax(int u, int l, int r, ll x) {
    if (tree[u].l >= l && tree[u].r <= r) {
        // 实际值 <= x → 原始值 <= x - add
        ll target = x - tree[u].add;
        ll L, H;
        calc_range(tree[u], L, H);
        if (H <= target) return;  // 已满足，无需更新
        if (L > target) {         // 整个区间都需更新为target
            tree[u].set_high = min(tree[u].set_high, target);
            tree[u].min_val = x;
            tree[u].max_val = x;
            tree[u].sum = x * (tree[u].r - tree[u].l + 1);
            return;
        }
        // 部分更新，需修改标记并更新状态
        tree[u].set_high = min(tree[u].set_high, target);
        H = min(H, target);
        tree[u].max_val = H + tree[u].add;
        // sum无法直接计算，需后续push_down处理
        return;
    }
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    if (l <= mid) update_setmax(u << 1, l, r, x);
    if (r > mid) update_setmax(u << 1 | 1, l, r, x);
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
    tree[u].max_val = max(tree[u << 1].max_val, tree[u << 1 | 1].max_val);
    tree[u].min_val = min(tree[u << 1].min_val, tree[u << 1 | 1].min_val);
}

// 查询区间和
ll query_sum(int u, int l, int r) {
    if (tree[u].l >= l && tree[u].r <= r) {
        return tree[u].sum;
    }
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    ll res = 0;
    if (l <= mid) res += query_sum(u << 1, l, r);
    if (r > mid) res += query_sum(u << 1 | 1, l, r);
    return res;
}

// 查询区间最大值
ll query_max(int u, int l, int r) {
    if (tree[u].l >= l && tree[u].r <= r) {
        return tree[u].max_val;
    }
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    ll res = NEG_INF;
    if (l <= mid) res = max(res, query_max(u << 1, l, r));
    if (r > mid) res = max(res, query_max(u << 1 | 1, l, r));
    return res;
}

// 查询区间最小值
ll query_min(int u, int l, int r) {
    if (tree[u].l >= l && tree[u].r <= r) {
        return tree[u].min_val;
    }
    push_down(u);
    int mid = (tree[u].l + tree[u].r) >> 1;
    ll res = INF;
    if (l <= mid) res = min(res, query_min(u << 1, l, r));
    if (r > mid) res = min(res, query_min(u << 1 | 1, l, r));
    return res;
}

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

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

    cin >> m;
    while (m--) {
        int op, l, r;
        ll x;
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> x;
            update_add(1, l, r, x);
        } else if (op == 2) {
            cin >> l >> r >> x;
            update_setmin(1, l, r, x);
        } else if (op == 3) {
            cin >> l >> r >> x;
            update_setmax(1, l, r, x);
        } else if (op == 4) {
            cin >> l >> r;
            cout << query_sum(1, l, r) << '\n';
        } else if (op == 5) {
            cin >> l >> r;
            cout << query_max(1, l, r) << '\n';
        } else if (op == 6) {
            cin >> l >> r;
            cout << query_min(1, l, r) << '\n';
        }
    }

    return 0;
}

代码说明

• 线段树构建：初始化每个节点的区间范围、和、最大/最小值，以及初始标记（无加法、无上下界）。
• 标记下放：确保子节点继承父节点的标记，更新子节点的状态后再处理子节点，保证操作正确性。
• 更新操作：
  • update_add：直接更新加法标记，调整和、最大/最小值。
  • update_setmin/update_setmax：转换为原始值的上下界标记，根据区间状态（完全满足、完全不满足、部分满足）更新节点。
• 查询操作：递归遍历线段树，合并子节点结果返回区间和、最大/最小值。

该实现通过高效的标记管理，确保每种操作的时间复杂度为O(log n)，能应对5×10^5规模的输入。