// Example solution for UVA 12086 // Pedro Ribeiro (DCC/FCUP) #include <cstdio> #define MAX 200005 #define MAX_BUF 16 #define MAX_ST 1000000 #define NEUTRAL 0 int n; // Number of elements int v[MAX]; // Array of values int st[MAX_ST]; // Segment tree (in this case storing sum of intervals) int merge(int a, int b) { return a+b; } // Build initial segment tree (in position node, interval [start,end]) void build(int i, int start, int end) { if (start == end) { st[i] = v[start]; } else { int m = start + (end-start)/2; build(i*2, start, m); build(i*2+1, m+1, end); st[i] = merge(st[i*2], st[i*2+1]); } // printf("%d (%d,%d) -> %d\n", i, start, end, st[i]); } // Make a query of interval [x,y] int query(int i, int start, int end, int a, int b) { if (start > b || end < a) return NEUTRAL; // Neutral element if (start >=a && end <=b) return st[i]; int m = start + (end-start)/2; int r1 = query(i*2, start, m, a, b); int r2 = query(i*2+1, m+1, end, a, b); return merge(r1, r2); } void update(int i, int start, int end, int x, int val) { // printf("%d (%d,%d) pos=%d change to %d\n", i, start, end, x, val); if (start == end && start == x) {st[i] = val; return;} if (start > x || end <x) return; int m = start + (end-start)/2; update(i*2, start, m, x, val); update(i*2+1, m+1, end, x, val); st[i] = merge(st[i*2], st[i*2+1]); } // Update node x with value val int main() { int c = 0; char op[MAX_BUF]; while (1) { scanf("%d", &n); if (n == 0) break; if (c > 0) putchar('\n'); printf("Case %d:\n", ++c); for (int i=1; i<=n; i++) scanf("%d", &v[i]); build(1, 1, n); while (1) { scanf("%s", op); if (op[0]=='M') { int a, b; scanf("%d %d", &a, &b); printf("%d\n", query(1, 1, n, a, b)); //printf("!! M %d %d\n", a, b); } else if (op[0]=='S') { int x, val; scanf("%d %d", &x, &val); update(1, 1, n, x, val); //printf("!! S %d %d\n", x, v); } else if (op[0]=='E') break; } } return 0; }