SP11470 TTM - To the moon

DAMDAM · 2024-08-12 22:15:44 · 题解

想到的不是可持久化线段树与标记永久化，而是可持久化平衡树。

所以想用这个做法，首先你得会平衡树、可持久化平衡树、文艺平衡树与可持久化文艺平衡树，最好再练几道题。

做法与模板题一样的，不过把翻转标记换成了加法标记。

区间加法怎么打标记呢？

非常显然的有

void TagAdd(Vertex *p, const ll &c) {
    p && (p->add += c, p->sum += c * p->siz, p->val += c);
}

即我们把该节点本身的值加上 c，该节点的标记加上 c，区间和加上 c\times siz。

那么之后只是裸的维护可持久化平衡树了。

建树用了 \Theta(n) 写法。

维护当前时间戳，可以用一个表示时间的变量来表示。

#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
struct Vertex {
    ll val = 0, sum = 0, add = 0;
    int siz = 0, cnt = 0;
    unsigned rank = 0;
    Vertex *son[2] = {};
    Vertex(const ll &__val = 0) { val = sum = __val, son[add = 0] = son[siz = cnt = 1] = nullptr; }
    Vertex* Copy() { return this ? &(*(new Vertex) = *this) : nullptr; }
} *rt[maxn];

int siz(Vertex *p) { return p ? p->siz : 0; }

ll sum(Vertex *p) { return p ? p->sum : 0; }

void Pushup(Vertex *p) { p && (p->siz = siz(*p->son) + siz(p->son[1]) + p->cnt, p->sum = sum(*p->son) + sum(p->son[1]) + p->val); }

void Maintain(Vertex *&p) { p && (p = p->Copy()); }

void TagAdd(Vertex *p, const ll &c) {
    p && (p->add += c, p->sum += c * p->siz, p->val += c);
}

void Pushdown(Vertex *p) {
    if (p && p->add) {
        Maintain(*p->son), Maintain(p->son[1]);
        p->add && (TagAdd(*p->son, p->add), TagAdd(p->son[1], p->add), p->add = 0);
    }
}

void SplitRank(const int &k, Vertex *&u, Vertex *&v, Vertex *p) {
    if (!p) return void(u = v = nullptr);
    Pushdown(p);
    if (k <= siz(*p->son)) v = p->Copy(), SplitRank(k, u, v->son[0], p->son[0]), Pushup(v);
    else u = p->Copy(), SplitRank(k - siz(*p->son) - p->cnt, u->son[1], v, p->son[1]), Pushup(u);
}

void Merge(Vertex *u, Vertex *v, Vertex *&p) {
    if (!u || !v) return void(p = u ? u : v);
    Pushdown(u), Pushdown(v);
    if (u->rank >= v->rank) p = v, Merge(u, p->son[0], p->son[0]);
    else p = u, Merge(p->son[1], v, p->son[1]);
    Pushup(p);
}

int n;
ll a[maxn];
void Build(const int &s = 1, const int &t = n, Vertex *&v = *rt, Vertex *u = nullptr) {
    if (s > t) return;
    int mid = s + ((t - s) >> 1);
    v = new Vertex{a[mid]}, v->rank = u ? u->rank + 1 : 0;
    if (s == t) return;
    Build(s, mid - 1, v->son[0], v), Build(mid + 1, t, v->son[1], v);
    Pushup(v);
}

void Add(const int &l, const int &r, const ll &x, Vertex *u, Vertex *&v) {
    Vertex *a = nullptr, *b = nullptr, *c = nullptr;
    SplitRank(l - 1, a, c, u), SplitRank(r - l + 1, b, c, c);
    TagAdd(b, x);
    Merge(b, c, c), Merge(a, c, v);
}

ll Get(const int &l, const int &r, Vertex *u) {
    Vertex *a = nullptr, *b = nullptr, *c = nullptr;
    SplitRank(l - 1, a, c, u), SplitRank(r - l + 1, b, c, c);
    ll reply = b->sum;
    return Merge(b, c, c), Merge(a, c, u), reply;
}

int m, now;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
    Build();
    char c;
    for (int l, r, x; m; --m) {
        scanf(" %c%d", &c, &l);
        if (c == 'B') now = l;
        else {
            scanf("%d", &r);
            if (c == 'Q') printf("%lld", Get(l, r, rt[now])), putchar(10);
            else {
                scanf("%d", &x);
                if (c == 'H') printf("%lld", Get(l, r, rt[x])), putchar(10);
                else Add(l, r, x, rt[now], rt[now + 1]), ++now;
            }
        }
    }
    return 0;
}