珂朵莉的最大子段和：Ynoi2018 末日时在做什么？有没有空？可以来拯救吗？

题目背景

今天真是多谢你了

让我体验了许多美好

我留下了如同美梦一般的回忆不过时间到了

最后我还想拜托你一件事

希望你可以把我忘掉

在自己消失之前

心怀不想消失的愿望

希望让某个人记住我

希望能留下羁绊

我这么希望着，又有什么不可以的吗

香香甜甜的，真好闻

看起来很好吃

我遵守了...

约...约定

我非常...非常努力哦...

欢迎回来，珂朵莉

题目描述

珂朵莉给了你一个长为 n 的序列 a，有 m 次操作。

把区间 [ l, r ] 内所有数都加上 x。
查询区间 [ l, r ] 内的最大子段和，可以不选数。

输入格式

第一行两个整数 n, m。

第二行 n 个整数表示序列 a。

后面 m 行：

1 l r x：把区间 [ l, r ] 内所有数加上 x。
2 l r：查询区间 [ l, r ] 的最大子段和。

输出格式

对于每个询问，输出一个数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

0
3
2

样例 #2

样例输入 #2

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

样例输出 #2

6
3
0

提示

Idea：nzhtl1477，Solution：ccz181078，Code：nzhtl1477&ccz181078&mrsrz，Data：nzhtl1477&mrsrz&w33z8kqrqk8zzzx33

$1 \le n , m \le 10^5$，$| a_i | \leq 10^9$，$|x|\leq 10^9$。

保证任意时刻 $|a_i|\leq 2\times 10^9$。

By nzhtl1477 & ccz181078 用C++内容：```cpp #include #include #include

using namespace std;

// 线段树节点结构体 struct Node { int left, right; // 节点表示的区间范围 int sum; // 节点表示的区间的和 int maxSum; // 节点表示的区间的最大子段和 int lazy; // 懒标记，表示该区间是否有更新操作 };

// 构建线段树 void buildTree(vector& a, vector& tree, int node, int left, int right) { tree[node].left = left; tree[node].right = right; if (left == right) { tree[node].sum = a[left]; tree[node].maxSum = max(0, a[left]); tree[node].lazy = 0; return; } int mid = (left + right) / 2; int leftChild = node * 2; int rightChild = node * 2 + 1; buildTree(a, tree, leftChild, left, mid); buildTree(a, tree, rightChild, mid + 1, right); tree[node].sum = tree[leftChild].sum + tree[rightChild].sum; tree[node].maxSum = max(max(tree[leftChild].maxSum, tree[rightChild].maxSum), tree[leftChild].sum + tree[rightChild].sum); tree[node].lazy = 0; }

// 更新节点的懒标记和区间和 void updateNode(vector& tree, int node, int delta) { tree[node].lazy += delta; tree[node].sum += (tree[node].right - tree[node].left + 1) * delta; tree[node].maxSum += delta; }

// 下传懒标记 void pushDown(vector& tree, int node) { if (tree[node].lazy != 0) { int leftChild = node * 2; int rightChild = node * 2 + 1; updateNode(tree, leftChild, tree[node].lazy); updateNode(tree, rightChild, tree[node].lazy); tree[node].lazy = 0; } }

// 更新节点的最大子段和 void updateMaxSum(vector& tree, int node) { int leftChild = node * 2; int rightChild = node * 2 + 1; tree[node].maxSum = max(max(tree[leftChild].maxSum, tree[rightChild].maxSum), tree[leftChild].sum + tree[rightChild].sum); }

// 区间更新 void updateRange(vector& tree, int node, int left, int right, int delta) { if (left <= tree[node].left && right >= tree[node].right) { updateNode(tree, node, delta); return; } pushDown(tree, node); int mid = (tree[node].left + tree[node].right) / 2; int leftChild = node * 2; int rightChild = node * 2 + 1; if (left <= mid) { updateRange(tree, leftChild, left, right, delta); } if (right > mid) { updateRange(tree, rightChild, left, right, delta); } updateMaxSum(tree, node); }

// 区间查询 int queryRange(vector& tree, int node, int left, int right) { if (left <= tree[node].left && right >= tree[node].right) { return tree[node].maxSum; } pushDown(tree, node); int mid = (tree[node].left + tree[node].right) / 2; int leftChild = node * 2; int rightChild = node * 2 + 1; int result = 0; if (left <= mid) { result = max(result, queryRange(tree, leftChild, left, right)); } if (right > mid) { result = max(result, queryRange(tree, rightChild, left, right)); } return result; }

int main() { int n, m; cin >> n >> m;

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

vector<Node> tree(4 * n + 1);
buildTree(a, tree, 1, 1, n);

for (int i = 0; i < m; i++) {
    int op, l, r, x;
    cin >> op >> l >> r;
    if (op == 1) {
        cin >> x;
        updateRange(tree, 1, l, r, x);
    } else if (op == 2) {
        int maxSum = queryRange(tree, 1, l, r);
        cout << maxSum << endl;
    }
}

return 0;

}