HDU 4348 To the moon 主席树

题意:

给出一个长度为\(n(n \leq 10^5)\)的序列，最开始时间\(t=0\)，支持下面几个操作：

\(C \, l \, r \, d\)：将区间\([l,r]\)每个数都加上\(d\)，并且时间\(t\)增加1秒
\(Q \, l \, r\)：查询当前时间区间\([l,r]\)所有元素之和
\(H \, l \, r \, t\)：查询时间为\(t\)时，区间\([l,r]\)的所有元素之和
\(B \, t\)：时间回溯到\(t\)

输出每次查询的结果。

分析：

这是支持区间修改的可持久化线段树。

我们维护一个\(sum\)表示区间的元素和以及一个懒惰标记\(add\)。

由于是主席树，查询时如果要\(pushdown\)就会新增节点，空间开销比较大。

所以查询时不进行\(pushdown\)，而是累加所经过的节点的\(add\)值乘上查询区间长度。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 100000 + 10;

struct Node

{

    int lch, rch, add;

    LL sum;

};

int sz;

Node T[maxn << 5];

int n, m, root[maxn];

LL S[maxn];

char op[5];

int update(int pre, int L, int R, int qL, int qR, int v) {

    int rt = ++sz;

    T[rt] = T[pre];

    T[rt].sum += (LL)v * (min(R, qR) - max(L, qL) + 1);

    if(qL <= L && R <= qR) { T[rt].add += v; return rt; }

    int M = (L + R) / 2;

    if(qL <= M) T[rt].lch = update(T[pre].lch, L, M, qL, qR, v);

    if(qR > M) T[rt].rch = update(T[pre].rch, M+1, R, qL, qR, v);

    return rt;

}

LL query(int rt, int L, int R, int qL, int qR) {

    if(qL <= L && R <= qR) return T[rt].sum;

    LL ans = (LL)T[rt].add * (min(R, qR) - max(L, qL) + 1);

    int M = (L + R) / 2;

    if(qL <= M) ans += query(T[rt].lch, L, M, qL, qR);

    if(qR > M) ans += query(T[rt].rch, M+1, R, qL, qR);

    return ans;

}

int main()

{

    bool flag = false;

    while(scanf("%d%d", &n, &m) == 2) {

        if(flag) puts(""); flag = true;

        for(int i = 1; i <= n; i++) {

            scanf("%lld", S + i);

            S[i] += S[i - 1];

        }

        sz = 0;

        int time = 0;

        while(m--) {

            scanf("%s", op);

            int l, r, d; scanf("%d", &l);

            if(op[0] == 'C') {

                scanf("%d%d", &r, &d);

                time++;

                root[time] = update(root[time - 1], 1, n, l, r, d);

            } else if(op[0] == 'Q') {

                scanf("%d", &r);

                LL ans = S[r] - S[l - 1];

                ans += query(root[time], 1, n, l, r);

                printf("%lld\n", ans);

            } else if(op[0] == 'H') {

                scanf("%d%d", &r, &d);

                LL ans = S[r] - S[l - 1];

                ans += query(root[d], 1, n, l, r);

                printf("%lld\n", ans);

            } else {

                time = l;

            }

        }

    }

    return 0;

}

巴特西

HDU 4348 To the moon 主席树

题意:

分析：

最新文章

热门文章