二次联通门 : luogu P2068 统计和
/* luogu P2068 统计和 线段树 单点修改 + 区间查询总和 5min才写完。。。被syl完虐 其单身 N * INF 的手速实在比不上。。 */ #include <cstdio> #define Max 1000005 void read (int &now) { now = 0; bool flag = false; register char word = getchar (); while (word < '0' || word > '9') { if (word == '-') flag = true; word = getchar (); } while (word >= '0' && word <= '9') { now = now * 10 + word - '0'; word = getchar (); } if (flag) now = -now; } struct Segment { struct Segment_Tree { int l; int r; int Sum; int Mid; }; Segment_Tree tree[Max << 2]; void Build (int l, int r, int now) { tree[now].l = l; tree[now].r = r; if (l == r) return ; tree[now].Mid = (l + r) >> 1; Build (l, tree[now].Mid, now << 1); Build (tree[now].Mid + 1, r, now << 1 | 1); } void Change_single (int pos, int now, int number) { if (tree[now].l == tree[now].r) { tree[now].Sum += number; return ; } if (pos <= tree[now].Mid) Change_single (pos, now << 1, number); else Change_single (pos, now << 1 | 1, number); tree[now].Sum = tree[now << 1].Sum + tree[now << 1 | 1].Sum; } int Query_Section_sum (int l, int r, int now) { if (tree[now].l == l && tree[now].r == r) return tree[now].Sum; if (r <= tree[now].Mid) return Query_Section_sum (l, r, now << 1); else if (l > tree[now].Mid) return Query_Section_sum (l, r, now << 1 | 1); else return Query_Section_sum (l, tree[now].Mid, now << 1) + Query_Section_sum (tree[now].Mid + 1, r, now << 1 | 1); } }; Segment Tree; int N; int pos; int main (int argc, char *argv[]) { char type[5]; read (N); Tree.Build (1, N, 1); read (N); int x, y; while (N--) { scanf ("%s", type); read (x); read (y); if (type[0] == 'x') Tree.Change_single (x, 1, y); else printf ("%d ", Tree.Query_Section_sum (x, y, 1)); } return 0; }