大意略。
思路:线段树入门题。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int maxn = 50010; int sum[maxn<<2]; int ql, qr; int p, v; int n; void pushup(int o) { sum[o] = sum[o*2] + sum[o*2+1]; } void build(int o, int L, int R) { int M = L + (R-L)/2; if(L == R) scanf("%d", &sum[o]); else { build(o*2, L, M); build(o*2+1, M+1, R); pushup(o); } } int query(int o, int L, int R) { int M = L + (R-L)/2, ans = 0; if(ql <= L && R <= qr) return sum[o]; if(ql <= M) ans += query(o*2, L, M); if(M < qr) ans += query(o*2+1, M+1, R); return ans; } void update(int o, int L, int R, int flag) { int M = L + (R-L)/2; if(L == R) sum[o] += flag? v : -v; else { if(p <= M) update(o*2, L, M, flag); else update(o*2+1, M+1, R, flag); pushup(o); } } void read_case() { scanf("%d", &n); build(1, 1, n); } void solve() { char opt[11]; read_case(); for(;;) { scanf("%s", opt); if(opt[0] == 'Q') { scanf("%d%d", &ql, &qr); printf("%d\n", query(1, 1, n)); } else if(opt[0] == 'S') { scanf("%d%d", &p, &v); update(1, 1, n, 0); } else if(opt[0] == 'A') { scanf("%d%d", &p, &v); update(1, 1, n, 1); } else break; } } int main() { int T, times = 0; scanf("%d", &T); while(T--) { printf("Case %d:\n", ++times); solve(); } return 0; }