題目描述

給定一個長度為?n?的序列?a，要求支持如下三個操作：

1. 給定區間?[l,r]，將區間內每個數都修改為?x。
2. 給定區間?[l,r]，將區間內每個數都加上?x。
3. 給定區間?[l,r]，求區間內的最大值。

輸入格式

第一行是兩個整數，依次表示序列的長度?n?和操作的個數?q。
第二行有?n?個整數，第?i?個整數表示序列中的第?i?個數?ai?。
接下來?q?行，每行表示一個操作。每行首先有一個整數?op，表示操作的類型。

• 若?op=1，則接下來有三個整數?l,r,x，表示將區間?[l,r]?內的每個數都修改為?x。
• 若?op=2，則接下來有三個整數?l,r,x，表示將區間?[l,r]?內的每個數都加上?x。
• 若?op=3，則接下來有兩個整數?l,r，表示查詢區間?[l,r]?內的最大值。

輸出格式

對于每個?op=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%?的數據，n=q=1。
• 對于?40%?的數據，n,q≤103。
• 對于?50%?的數據，0≤ai?,x≤104。
• 對于?60%?的數據，op=1。
• 對于?90%?的數據，n,q≤105。
• 對于?100%?的數據，1≤n,q≤106，1≤l,r≤n，op∈{1,2,3}，∣ai?∣,∣x∣≤109。

提示

請注意大量數據讀入對程序效率造成的影響。

代碼實現：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;

struct SegmentTreeNode {
? ? ll max_val;
? ? ll add;
? ? ll set;
? ? bool has_set;
};

class SegmentTree {
private:
? ? vector<SegmentTreeNode> tree;
? ? int n;
? ? vector<ll> arr;

? ? void build(int node, int start, int end) {
? ? ? ? tree[node].add = 0;
? ? ? ? tree[node].has_set = false;
? ? ? ? if (start == end) {
? ? ? ? ? ? tree[node].max_val = arr[start - 1];
? ? ? ? ? ? tree[node].set = arr[start - 1];
? ? ? ? } else {
? ? ? ? ? ? int mid = (start + end) / 2;
? ? ? ? ? ? build(2 * node, start, mid);
? ? ? ? ? ? build(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) {
? ? ? ? int mid = (start + end) / 2;
? ? ? ? int left_node = 2 * node;
? ? ? ? int right_node = 2 * node + 1;

? ? ? ? if (tree[node].has_set) {
? ? ? ? ? ? tree[left_node].max_val = tree[node].set;
? ? ? ? ? ? tree[right_node].max_val = tree[node].set;
? ? ? ? ? ? tree[left_node].set = tree[node].set;
? ? ? ? ? ? tree[right_node].set = tree[node].set;
? ? ? ? ? ? tree[left_node].add = 0;
? ? ? ? ? ? tree[right_node].add = 0;
? ? ? ? ? ? tree[left_node].has_set = true;
? ? ? ? ? ? tree[right_node].has_set = true;
? ? ? ? ? ? tree[node].has_set = false;
? ? ? ? }

? ? ? ? if (tree[node].add != 0) {
? ? ? ? ? ? tree[left_node].max_val += tree[node].add;
? ? ? ? ? ? tree[right_node].max_val += tree[node].add;
? ? ? ? ? ? if (tree[left_node].has_set) {
? ? ? ? ? ? ? ? tree[left_node].set += tree[node].add;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? tree[left_node].add += tree[node].add;
? ? ? ? ? ? }
? ? ? ? ? ? if (tree[right_node].has_set) {
? ? ? ? ? ? ? ? tree[right_node].set += tree[node].add;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? tree[right_node].add += tree[node].add;
? ? ? ? ? ? }
? ? ? ? ? ? tree[node].add = 0;
? ? ? ? }
? ? }

? ? void update_set(int node, int start, int end, int l, int r, ll x) {
? ? ? ? if (r < start || l > end) {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? if (l <= start && end <= r) {
? ? ? ? ? ? tree[node].max_val = x;
? ? ? ? ? ? tree[node].set = x;
? ? ? ? ? ? tree[node].add = 0;
? ? ? ? ? ? tree[node].has_set = true;
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? push_down(node, start, end);
? ? ? ? int mid = (start + end) / 2;
? ? ? ? update_set(2 * node, start, mid, l, r, x);
? ? ? ? update_set(2 * node + 1, mid + 1, end, l, r, x);
? ? ? ? tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
? ? }

? ? void update_add(int node, int start, int end, int l, int r, ll x) {
? ? ? ? if (r < start || l > end) {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? if (l <= start && end <= r) {
? ? ? ? ? ? tree[node].max_val += x;
? ? ? ? ? ? if (tree[node].has_set) {
? ? ? ? ? ? ? ? tree[node].set += x;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? tree[node].add += x;
? ? ? ? ? ? }
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? push_down(node, start, end);
? ? ? ? int mid = (start + end) / 2;
? ? ? ? update_add(2 * node, start, mid, l, r, x);
? ? ? ? update_add(2 * node + 1, mid + 1, end, l, r, x);
? ? ? ? tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
? ? }

? ? ll query_max(int node, int start, int end, int l, int r) {
? ? ? ? if (r < start || l > end) {
? ? ? ? ? ? return LLONG_MIN;
? ? ? ? }
? ? ? ? if (l <= start && end <= r) {
? ? ? ? ? ? return tree[node].max_val;
? ? ? ? }
? ? ? ? push_down(node, start, end);
? ? ? ? int mid = (start + end) / 2;
? ? ? ? ll left_max = query_max(2 * node, start, mid, l, r);
? ? ? ? ll right_max = query_max(2 * node + 1, mid + 1, end, l, r);
? ? ? ? return max(left_max, right_max);
? ? }

public:
? ? SegmentTree(const vector<ll>& a) {
? ? ? ? arr = a;
? ? ? ? n = arr.size();
? ? ? ? tree.resize(4 * n);
? ? ? ? build(1, 1, n);
? ? }

? ? void set_range(int l, int r, ll x) {
? ? ? ? update_set(1, 1, n, l, r, x);
? ? }

? ? void add_range(int l, int r, ll x) {
? ? ? ? update_add(1, 1, n, l, r, x);
? ? }

? ? ll get_max(int l, int r) {
? ? ? ? return query_max(1, 1, n, l, r);
? ? }
};

int main() {
? ? ios_base::sync_with_stdio(false);
? ? cin.tie(NULL);

? ? int n, q;
? ? cin >> n >> q;

? ? vector<ll> a(n);
? ? for (int i = 0; i < n; ++i) {
? ? ? ? cin >> a[i];
? ? }

? ? SegmentTree st(a);

? ? for (int i = 0; i < q; ++i) {
? ? ? ? int op;
? ? ? ? cin >> op;
? ? ? ? if (op == 1) {
? ? ? ? ? ? int l, r;
? ? ? ? ? ? ll x;
? ? ? ? ? ? cin >> l >> r >> x;
? ? ? ? ? ? st.set_range(l, r, x);
? ? ? ? } else if (op == 2) {
? ? ? ? ? ? int l, r;
? ? ? ? ? ? ll x;
? ? ? ? ? ? cin >> l >> r >> x;
? ? ? ? ? ? st.add_range(l, r, x);
? ? ? ? } else if (op == 3) {
? ? ? ? ? ? int l, r;
? ? ? ? ? ? cin >> l >> r;
? ? ? ? ? ? cout << st.get_max(l, r) << endl;
? ? ? ? }
? ? }

? ? return 0;
} ? ?