02/1
19:52
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 }.
Input
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 }.
Output
For each query, print an integer as the problem required.
Example
Input:
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3Output:
6
4
-3
还是最大连续子段和,只是加了修改操作,同GSS1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> #include <cstdio> #include <algorithm> #define lson (now << 1) #define rson (now << 1 | 1) using namespace std; typedef long long LL; const int SZ = 5e4 + 10; struct SGT { int l, r; LL sum, lmax, rmax, allmax; }tree[SZ * 4]; int num[SZ]; void read(int &num) { num = 0; char c = getchar(); int f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while('0' <= c && c <= '9') {num = num * 10 + (c - '0'); c = getchar();} num *= f; } void update(int now) { tree[now].sum = tree[lson].sum + tree[rson].sum; tree[now].lmax = max(tree[lson].lmax, tree[lson].sum + tree[rson].lmax); tree[now].rmax = max(tree[rson].rmax, tree[rson].sum + tree[lson].rmax); tree[now].allmax = max(tree[lson].rmax + tree[rson].lmax, max(tree[lson].allmax, tree[rson].allmax)); } void build(int now, int l, int r) { tree[now].l = l; tree[now].r = r; if(l == r) { tree[now].sum = tree[now].lmax = tree[now].rmax = tree[now].allmax = num[l]; return ; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); update(now); } void change(int now, int pos, int value) { if(tree[now].l == tree[now].r) { tree[now].sum = tree[now].lmax = tree[now].rmax = tree[now].allmax = value; return ; } int mid = (tree[now].l + tree[now].r) >> 1; if(pos <= mid) change(lson, pos, value); else change(rson, pos, value); update(now); } SGT ask(int now, int l, int r) { if(l == tree[now].l && tree[now].r == r) return tree[now]; int mid = (tree[now].l + tree[now].r) >> 1; if(r <= mid) return ask(lson, l, r); if(l > mid) return ask(rson, l, r); SGT AskL = ask(lson, l, mid), AskR = ask(rson, mid + 1, r); SGT ans; ans.sum = AskL.sum + AskR.sum; ans.lmax = max(AskL.lmax, AskL.sum + AskR.lmax); ans.rmax = max(AskR.rmax, AskR.sum + AskL.rmax); ans.allmax = max(AskL.rmax + AskR.lmax, max(AskL.allmax, AskR.allmax)); return ans; } int main() { int n, m; read(n); for(int i = 1; i <= n; i++) read(num[i]); build(1, 1, n); read(m); int op, a, b; while(m--) { read(op), read(a), read(b); if(!op) change(1, a, b); else printf("%lld\n", ask(1, a, b).allmax); } return 0; } |