POJ 3468_PERSISTENTTAG

题目大意

暂无

题目解法

暂无

RTFC

#include <cctype>
#include <cstdio>
#define C(x) ((x) = getchar())
#define L(x) ((x) << 1)
#define R(x) ((x) << 1 | 1)
#define avg(x, y) (((x) + (y)) >> 1)
typedef long long i64;
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void read(int &x)
{
    int ch = x = 0, sign = 1;
    while (!isdigit(C(ch))) if (ch == '-') sign = -1;
    for (; isdigit(ch); C(ch))
        x = x * 10 + ch - '0';
    x *= sign;
}
const int N = int(1e5 + 5);
i64 add[N << 2], sum[N << 2];
int a[N];
void build(int k, int l, int r)
{
    if (l == r - 1) return void(sum[k] = a[l]);
    int m = avg(l, r);
    build(L(k), l, m);
    build(R(k), m, r);
    sum[k] = sum[L(k)] + sum[R(k)];
}
void modify(int k, int l, int r, int x, int y, int v)
{
    if (x <= l && r <= y)
        return void(add[k] += v);
    sum[k] += 1ll * (min(r, y) - max(l, x)) * v;
    int m = avg(l, r);
    if (x < m) modify(L(k), l, m, x, y, v);
    if (y > m) modify(R(k), m, r, x, y, v);
}
i64 query(int k, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return sum[k] + (r - l) * add[k];
    int m = avg(l, r);
    i64 res = add[k] * (min(r, y) - max(l, x));
    if (x < m) res += query(L(k), l, m, x, y);
    if (y > m) res += query(R(k), m, r, x, y);
    return res;
}
int main()
{
    int n, m;
    read(n), read(m);
    for (int i = 0; i < n; i++) read(a[i]);
    build(1, 0, n);
    while (m--)
    {
        int op = 0, x, y, z;
        while (op != 'C' && op != 'Q') C(op);
        if (op == 'Q')
        {
            read(x), read(y);
            printf("%lld\n", query(1, 0, n, x - 1, y));
        }
        else
        {
            read(x), read(y), read(z);
            modify(1, 0, n, x - 1, y, z);
        }
    }
    return  0;
}