题目描述

现有一序列$A$。您需要实现一棵可持久化线段树，用于实现如下操作：

• A v p x：对于版本v的序列，给$A_p$增加$x$.
• Q v l r：对于版本v的序列，询问$A_{[l,r]}$的区间和。
• C v：拷贝一份版本v的序列，编号为当前版本总数+1.

注意版本号从$1$开始；版本$1$的序列，所有元素均为$0$.

格式

输入格式

第一行，两个正整数$n,t$，表示序列的长度和操作个数。
接下来$t$行，每行一个操作，格式如题目描述所述。

保证任何输入的数都是正整数。

输出格式

对于每一个Q操作，输出一行一个整数，表示对应的区间和。

样例数据

样例输入

5 5
A 1 2 3
Q 1 1 4
C 1
A 2 3 2
Q 2 1 4

样例输出

3
5

解释

第一次操作后，版本1的序列为：0 3 0 0 0.
第二次操作询问版本1的$A_{[1,4]}$区间和，答案为$0+3+0+0=3$.
第三次操作将版本1的序列复制到版本2.
第四次操作后，版本2的序列为：0 3 2 0 0.
第五次操作询问版本2的$A_{[1,4]}$区间和，答案为$0+3+2+0=5$.

数据规模与约定

对于$20\%$的数据，有$n \leq 1000 , m \leq 100$.
对于$60\%$的数据，有$n \leq 100000 , m \leq 1000$.
对于$100\%$的数据，有$n \leq 1000000 , m \leq 1000000$.

题解

100w，直接写主席树会被卡空间。由于每一个版本是从之前的版本“衍生”出来的。所以我们只需要维护一个版本——“当前”的版本。对于修改操作，我们在处理完这个版本之后将它还原；对于查询操作，直接在当前的线段树里面查询；对于衍生操作，我们递归下去。正确性是显然的，这样我们就卡过了空间。把上文的线段树改成树状数组，就可以卡过时间。

转自阮行止

下附我的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>

using namespace std;

typedef long long LL;

inline int Read() {
    char c;
    while (c = getchar(), !isdigit(c));
    int x = c - 48;
    while (c = getchar(), isdigit(c)) x = x * 10 + c - 48;
    return x;
}
inline void Read(int &x) {
    char c;
    while (c = getchar(), !isdigit(c));
    x = c - 48;
    while (c = getchar(), isdigit(c)) x = x * 10 + c - 48;
    return;
}
inline void Writeln(LL x) {
    int k = 0, t[20];
    do t[++k] = x % 10 + 48;
    while (x /= 10);
    while (k) putchar(t[k--]);
    putchar('\n');
    return;
}

const int N = 1000010, M = 1000010;

int n, m;
char ch[10];
LL a[N];
inline int Lowbit(int x) {
    return (x) & (-x);
}
void Modify(int x, int k) {
    for (; x <= n; x += Lowbit(x))
        a[x] += k;
    return;
}
LL Sum(int x) {
    LL sum = 0;
    for (; x; x -= Lowbit(x))
        sum += a[x];
    return sum;
}

int tot = -1, head[M], tail[N];
struct Edge {
    int t, x, k, next;
} edge[M];
inline void Add(int u, int t, int x, int k = 0) {
    edge[++tot] = (Edge) {t, x, k, -1};
    if (!~head[u]) head[u] = tot;
    else edge[tail[u]].next = tot;
    tail[u] = tot;
    return;
}
LL res[M];

void DFS(int u) {
    for (int i = head[u]; ~i; i = edge[i].next) {
        int t = edge[i].t;
        if (t == 1) Modify(edge[i].x, edge[i].k);
        else if (t == 2) res[i] = Sum(edge[i].k) - Sum(edge[i].x - 1);
        else DFS(edge[i].x);
    }
    for (int i = head[u]; ~i; i = edge[i].next)
        if (edge[i].t == 1) Modify(edge[i].x, -edge[i].k);
    return;
}

int main() {
    Read(n);
    Read(m);
    memset(head, -1, sizeof(head));
    int cnt = 1;
    for (int i = 1; i <= m; ++i) {
        scanf("%s", ch);
        if (ch[0] == 'A') {
            int v = Read(), x = Read(), k = Read();
            Add(v, 1, x, k);
        } else if (ch[0] == 'Q') {
            int v = Read(), l = Read(), r = Read();
            Add(v, 2, l, r);
        } else {
            int v = Read();
            Add(v, 3, ++cnt);
        }
    }
    DFS(1);
    for (int i = 0; i < m; ++i)
        if (edge[i].t == 2) Writeln(res[i]);
    return 0;
}