SPOJ - HORRIBLE 【线段树】

思路

线段树 区间更新 模板题 注意数据范围

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;LL t, n, q;
LL anssum;struct Node
{LL l, r;LL addv, sum;
}tree[maxn << 2];void maintain(LL id)
{if (tree[id].l >= tree[id].r)return;tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
}void pushdown(LL id)
{if (tree[id].l >= tree[id].r)return;if (tree[id].addv){LL 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(LL 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(LL 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(LL 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("%lld", &t);while (t--){scanf("%lld %lld", &n, &q);build(1, 1, n);LL id;LL x, y;LL val;while (q--){scanf("%lld", &id);if (id == 0){scanf("%lld %lld %lld", &x, &y, &val);updateAdd(1, x, y, val);}else if (id == 1){scanf("%lld %lld", &x, &y);anssum = 0;query(1, x, y);cout << anssum << endl;}}}
}