POJ 3468 A Simple Problem with Integers——区间更新的线段树

POJ 3468 A Simple Problem with Integers——区间更新的线段树

模板题

#include #include #include #include using namespace std;typedef long long ll;const int maxn = 1e5 + 10;ll n, q, date[maxn], segTree[maxn<<2], lazy[maxn<<2];void pushup(ll root) { segTree[root] = segTree[root<<1] + segTree[root<<1|1];}void pushdown(ll root, ll cntL, ll cntR) { if (lazy[root]) { lazy[root<<1] += lazy[root]; lazy[root<<1|1] += lazy[root]; segTree[root<<1] += lazy[root] * cntL; segTree[root<<1|1] += lazy[root] *cntR; lazy[root] = 0; }}void build(ll L, ll R, ll root) { if (L == R) { segTree[root] = date[L]; return; } ll mid = (L + R)>>1; build(L, mid, root<<1); build(mid + 1, R, root<<1|1); pushup(root);}void update_interval(ll L, ll R, ll root, ll uL, ll uR, ll val) { if (uL <= L && R <= uR) { segTree[root] += val * (R - L + 1); lazy[root] += val; return; } ll mid = (L + R)>>1; pushdown(root, mid - L + 1, R - mid); if (uL <= mid) { update_interval(L, mid, root<<1, uL, uR, val); } if (uR > mid) { update_interval(mid + 1, R, root<<1|1, uL, uR, val); } pushup(root);}ll query(ll L, ll R, ll root, ll qL, ll qR) { if (qL <= L && R <= qR) { return segTree[root]; } ll mid = (L + R)>>1; pushdown(root, mid - L + 1, R - mid); ll ans = 0; if (qL <= mid) { ans += query(L, mid, root<<1, qL, qR); } if (qR > mid) { ans += query(mid + 1, R, root<<1|1, qL, qR); } return ans;}int main(){ while (scanf("%lld %lld", &n, &q) == 2) { for (int i = 1; i <= n; i++) { scanf("%lld", &date[i]); } memset(segTree, 0, sizeof(segTree)); memset(lazy, 0, sizeof(lazy)); build(1, n, 1); while (q--) { char c; cin >> c; if (c == 'Q') { int x, y; scanf("%d %d", &x, &y); if (x > y) swap(x, y); printf("%lld\n", query(1, n, 1, x, y)); } else if (c == 'C') { int x, y, z; scanf("%d %d %d", &x, &y, &z); if (x > y) swap(x, y); update_interval(1, n, 1, x, y, z); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。