p1253

题目描述

给定一个长度为 nn 的序列 aa，要求支持如下三个操作：

1. 给定区间 [l,r][l,r]，将区间内每个数都修改为 xx。
2. 给定区间 [l,r][l,r]，将区间内每个数都加上 xx。
3. 给定区间 [l,r][l,r]，求区间内的最大值。

输入格式

第一行是两个整数，依次表示序列的长度 nn 和操作的个数 qq。
第二行有 nn 个整数，第 ii 个整数表示序列中的第 ii 个数 aiai​。
接下来 qq 行，每行表示一个操作。每行首先有一个整数 opop，表示操作的类型。

• 若 op=1op=1，则接下来有三个整数 l,r,xl,r,x，表示将区间 [l,r][l,r] 内的每个数都修改为 xx。
• 若 op=2op=2，则接下来有三个整数 l,r,xl,r,x，表示将区间 [l,r][l,r] 内的每个数都加上 xx。
• 若 op=3op=3，则接下来有两个整数 l,rl,r，表示查询区间 [l,r][l,r] 内的最大值。

输出格式

对于每个 op=3op=3 的操作，输出一行一个整数表示答案。

输入输出样例

输入 #1复制

6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6

输出 #1复制

7
6
-1

输入 #2复制

4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4

输出 #2复制

0

说明/提示

数据规模与约定

• 对于 10%10% 的数据，n=q=1n=q=1。
• 对于 40%40% 的数据，n,q≤103n,q≤103。
• 对于 50%50% 的数据，0≤ai,x≤1040≤ai​,x≤104。
• 对于 60%60% 的数据，op≠1op=1。
• 对于 90%90% 的数据，n,q≤105n,q≤105。
• 对于 100%100% 的数据，1≤n,q≤1061≤n,q≤106，1≤l,r≤n1≤l,r≤n，op∈{1,2,3}op∈{1,2,3}，∣ai∣,∣x∣≤109∣ai​∣,∣x∣≤109。

提示

请注意大量数据读入对程序效率造成的影响。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // 包含 climits 头文件以使用 LLONG_MIN

using namespace std;

// 定义线段树节点结构体
struct Node {
    long long max_val;     // 当前区间的最大值
    long long lazy_set;    // 懒惰标记，表示区间内的所有元素都被设置为某个值（-1 表示无此操作）
    long long lazy_add;    // 懒惰标记，表示区间内的所有元素都加上某个值
};

// 线段树类
class SegmentTree {
public:
    int n;                 // 序列长度
    vector<Node> tree;     // 线段树数组

    // 构造函数，初始化线段树
    SegmentTree(int size) : n(size), tree(4 * size, Node{LLONG_MIN, -1, 0}) {}

    // 构建线段树
    void build(const vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node].max_val = arr[start]; // 叶子节点直接赋值
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node, start, mid);       // 构建左子树
            build(arr, 2 * node + 1, mid + 1, end); // 构建右子树
            tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val); // 更新当前节点的最大值
        }
    }

    // 下推懒惰标记
    void push_down(int node, int start, int end) {
        if (tree[node].lazy_set != -1) {
            // 如果存在区间设置操作，将该操作应用到子节点
            tree[2 * node].max_val = tree[node].lazy_set;
            tree[2 * node + 1].max_val = tree[node].lazy_set;
            tree[2 * node].lazy_set = tree[node].lazy_set;
            tree[2 * node + 1].lazy_set = tree[node].lazy_set;
            tree[2 * node].lazy_add = 0;
            tree[2 * node + 1].lazy_add = 0;
            tree[node].lazy_set = -1; // 清除当前节点的设置标记
        }
        if (tree[node].lazy_add != 0) {
            // 如果存在区间加法操作，将该操作应用到子节点
            tree[2 * node].max_val += tree[node].lazy_add;
            tree[2 * node + 1].max_val += tree[node].lazy_add;
            if (tree[2 * node].lazy_set == -1)
                tree[2 * node].lazy_add += tree[node].lazy_add;
            else
                tree[2 * node].lazy_set += tree[node].lazy_add;
            if (tree[2 * node + 1].lazy_set == -1)
                tree[2 * node + 1].lazy_add += tree[node].lazy_add;
            else
                tree[2 * node + 1].lazy_set += tree[node].lazy_add;
            tree[node].lazy_add = 0; // 清除当前节点的加法标记
        }
    }

    // 区间设置操作
    void update_range_set(int l, int r, long long val, int node, int start, int end) {
        if (l > end || r < start) return; // 区间不相交，无需更新
        if (l <= start && end <= r) {
            // 当前区间完全包含于目标区间，进行设置操作
            tree[node].max_val = val;
            tree[node].lazy_set = val;
            tree[node].lazy_add = 0;
            return;
        }
        push_down(node, start, end); // 下推懒惰标记
        int mid = (start + end) / 2;
        update_range_set(l, r, val, 2 * node, start, mid);       // 更新左子树
        update_range_set(l, r, val, 2 * node + 1, mid + 1, end); // 更新右子树
        tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val); // 更新当前节点的最大值
    }

    // 区间加法操作
    void update_range_add(int l, int r, long long val, int node, int start, int end) {
        if (l > end || r < start) return; // 区间不相交，无需更新
        if (l <= start && end <= r) {
            // 当前区间完全包含于目标区间，进行加法操作
            tree[node].max_val += val;
            if (tree[node].lazy_set == -1)
                tree[node].lazy_add += val;
            else
                tree[node].lazy_set += val;
            return;
        }
        push_down(node, start, end); // 下推懒惰标记
        int mid = (start + end) / 2;
        update_range_add(l, r, val, 2 * node, start, mid);       // 更新左子树
        update_range_add(l, r, val, 2 * node + 1, mid + 1, end); // 更新右子树
        tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val); // 更新当前节点的最大值
    }

    // 区间查询最大值操作
    long long query_max(int l, int r, int node, int start, int end) {
        if (l > end || r < start) return LLONG_MIN; // 区间不相交，返回最小值
        if (l <= start && end <= r) return tree[node].max_val; // 当前区间完全包含于目标区间，返回最大值
        push_down(node, start, end); // 下推懒惰标记
        int mid = (start + end) / 2;
        long long left_max = query_max(l, r, 2 * node, start, mid);       // 查询左子树
        long long right_max = query_max(l, r, 2 * node + 1, mid + 1, end); // 查询右子树
        return max(left_max, right_max); // 返回左右子树的最大值
    }
};

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

    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;

    SegmentTree st(n);
    st.build(a, 1, 0, n - 1); // 构建线段树

    while (q--) {
        int op, l, r;
        long long x;
        cin >> op >> l >> r;
        --l, --r; // 将索引转换为 0 基础
        if (op == 1) {
            cin >> x;
            st.update_range_set(l, r, x, 1, 0, n - 1); // 执行区间设置操作
        } else if (op == 2) {
            cin >> x;
            st.update_range_add(l, r, x, 1, 0, n - 1); // 执行区间加法操作
        } else if (op == 3) {
            cout << st.query_max(l, r, 1, 0, n - 1) << "\n"; // 执行区间查询最大值操作
        }
    }

    return 0;
}