PKU A Simple Problem with Integers 3468
April 27th, 2009
No comments
题目地址
对于Q操作，求出区间的总和，对于C操作，将区间里的所有数都加上同一个数
考虑结点存放两个信息，一个是该结点区间内的和s，一个是该区间所有数的增量d,对于一个C操作，如果区间刚好等于某结点的区间，则直接将增量加上去，否则，递归到左右子结点，并更新父结点的s值。这样，对于插入与查询都能达到O(logn)的复杂度.
Memory: 6760K
Time: 1579MS
#include <iostream> using namespace std; #define ll long long const int MAXN = 100001; struct { int l, r; ll s, d; } nod[MAXN*3]; int a[MAXN]; void creat(int t, int l, int r) { if(l == r) { nod[t].l = nod[t].r = l, nod[t].s = a[l], nod[t].d = 0; return; } int m = (l+r) / 2; nod[t].l = l, nod[t].r = r, nod[t].d = 0; creat(t*2, l, m), creat(t*2+1, m+1, r); nod[t].s = nod[t*2].s + nod[t*2+1].s; } void inc(int t, int l, int r, int c) { if(l == nod[t].l && r == nod[t].r) {nod[t].d += c; return;} if(r <= nod[t*2].r) inc(t*2, l, r, c); else if(l >= nod[t*2+1].l) inc(t*2+1, l, r, c); else inc(t*2, l, nod[t*2].r, c), inc(t*2+1, nod[t*2+1].l, r, c); nod[t].s = nod[t*2].s + nod[t*2].d * (nod[t*2].r-nod[t*2].l+1) + nod[t*2+1].s + nod[t*2+1].d * (nod[t*2+1].r-nod[t*2+1].l+1); } ll query(int t, int l, int r) { if(nod[t].l == l && nod[t].r == r) return nod[t].s + nod[t].d * (r-l+1); ll sum; if(r <= nod[t*2].r) sum = query(t*2, l, r); else if(l >= nod[t*2+1].l) sum = query(t*2+1, l, r); else sum = query(t*2, l, nod[t*2].r) + query(t*2+1, nod[t*2+1].l, r); return sum + nod[t].d * (r-l+1); } int main() { int i, n, q, x1, x2, c; char s[2]; while(scanf("%d%d", &n, &q) != EOF) { for(i = 1; i <= n; i++) scanf("%d", &a[i]); creat(1, 1, n); while(q--) { scanf("%s%d%d", s, &x1, &x2); if(s[0] == 'C') {scanf("%d", &c); inc(1, x1, x2, c);} else printf("%lld\n", query(1, x1, x2)); } } return 0; }
Recent Comments