题目描述
You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 +
.. + Aj | x<=i<=j<=y }.
输入格式
The first line of input
contains an integer N. The following line contains N integers, representing the
sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations
in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
输出格式
For each query, print an integer as the problem required.
题意翻译
n 个数，q 次操作
操作0 x y把Ax 修改为y
操作1 l r询问区间[l,r] 的最大子段和
输入输出样例
输入 #1 复制
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
输出 #1 复制
6
4
-3
一切尽在注释。需要特别注意的是ask函数和别的题不太一样。
#include <bits/stdc++.h> #define SIZE 50005 using namespace std; int a[SIZE], n, q; struct SegmentTree { int p; int l; int r; int sum; int dat; int lmax; int rmax; } t[4*SIZE]; void update(int p) { t[p].sum = t[2 * p].sum + t[2 * p + 1].sum; t[p].lmax = max(t[2 * p].lmax, t[2 * p].sum + t[2 * p + 1].lmax); t[p].rmax = max(t[2 * p + 1].rmax, t[2 * p].rmax + t[2 * p + 1].sum); t[p].dat = max(max(t[2 * p].dat, t[2 * p + 1].dat), t[2 * p].rmax + t[2 * p + 1].lmax); } void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if(l == r) { t[p].dat = t[p].sum = t[p].lmax = t[p].rmax = a[l]; return; } int mid = (l + r) >> 1; build(2 * p, l, mid); build(2 * p + 1, mid + 1, r); update(p); } void change(int p, int x, int v) { if(t[p].l == t[p].r) { t[p].dat = t[p].sum = t[p].lmax = t[p].rmax = v; return; }//递归边界是当前左右端点相等 int mid = (t[p].l + t[p].r) >> 1; if(x <= mid) change(2 * p, x, v);//l<=mid !!! else change(2 * p + 1, x, v); update(p); } SegmentTree ask(int p, int l, int r)//注意ask的返回类型，这个题不是直接返回答案 { if(l <= t[p].l && r >= t[p].r) return t[p];//包含在待询问区间内部 int mid = (t[p].l + t[p].r) >> 1; if(r <= mid) return ask(2 * p, l, r);//注意这里的参数还是l和r，因为待询问区间没有被mid分开 if(l > mid) return ask(2 * p + 1, l, r); //查询区间被mid分开了 SegmentTree left = ask(2 * p, l, mid), right = ask(2 * p + 1, mid + 1, r), node;//对询问区间进行调整 在这里设置一个临时节点node，因为之前没有节点能同时统计到mid左右两边各一部分的信息 node.sum = left.sum + right.sum;//类似update函数 node.lmax = max(left.lmax, left.sum + right.lmax); node.rmax = max(right.rmax, left.rmax + right.sum); node.dat = max(max(left.dat, right.dat), left.rmax + right.lmax); return node; } int main() { cin >> n; int i; for(i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); cin >> q; for(i = 1; i <= q; i++) { int c, a, b; scanf("%d%d%d", &c, &a, &b); if(c == 0) change(1, a, b); else cout << ask(1, a, b).dat<<endl; } return 0; }