POJ 3468 A Simple Problem with Integers 【线段树】

题目链接

http://poj.org/problem?id=3468

思路

线段树 区间更新 模板题 在赋初始值的时候，按点更新区间就可以

AC代码

#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <iostream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const double eps = 1e-6; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; int n, q; LL anssum; struct Node { LL l, r; LL addv, sum; }tree[maxn << 2]; void maintain(int id) { if (tree[id].l >= tree[id].r) return; tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum; } void pushdown(int id) { if (tree[id].l >= tree[id].r) return; if (tree[id].addv) { int tmp = tree[id].addv; tree[id << 1].addv += tmp; tree[id << 1 | 1].addv += tmp; tree[id << 1].sum += (tree[id << 1].r - tree[id << 1].l + 1) * tmp; tree[id << 1 | 1].sum += (tree[id << 1 | 1].r - tree[id << 1 | 1].l + 1) * tmp; tree[id].addv = 0; } } void build(int id, LL l, LL r) { tree[id].l = l; tree[id].r = r; tree[id].addv = 0; tree[id].sum = 0; if (l == r) { tree[id].sum = 0; return; } LL mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); maintain(id); } void updateAdd(int id, LL l, LL r, LL val) { if (tree[id].l >= l && tree[id].r <= r) { tree[id].addv += val; tree[id].sum += (tree[id].r - tree[id].l + 1) * val; return; } pushdown(id); LL mid = (tree[id].l + tree[id].r) >> 1; if (l <= mid) updateAdd(id << 1, l, r, val); if (mid < r) updateAdd(id << 1 | 1, l, r, val); maintain(id); } void query(int id, LL l, LL r) { if (tree[id].l >= l && tree[id].r <= r) { anssum += tree[id].sum; return; } pushdown(id); LL mid = (tree[id].l + tree[id].r) >> 1; if (l <= mid) query(id << 1, l, r); if (mid < r) query(id << 1 | 1, l, r); maintain(id); } int main() { scanf("%d %d", &n, &q); build(1, 1, n); for (LL i = 1; i <= n; i++) { LL num; cin >> num; updateAdd(1, i, i, num); } char id; LL x, y; LL val; while (q--) { scanf(" %c", &id); if (id == 'C') { scanf("%lld %lld %lld", &x, &y, &val); updateAdd(1, x, y, val); } else if (id == 'Q') { scanf("%lld %lld", &x, &y); anssum = 0; query(1, x, y); cout << anssum << endl; } } }

转载于:https://www.cnblogs.com/Dup4/p/9433279.html

相关资源：JAVA上百实例源码以及开源项目