【LCT】CSP 202109-5 箱根山岳险天下 LCT维护时间树

今天上完了人生最后一节化学课，泪目??，完结撒花??

这道题容易感觉是主席树but不是，因为操作仍然是对现在的点操作，问的答案也不是问历史答案而是现在的答案。

我们以排名为树的高度，就很容易想到一棵以时间为序依次加点的树。对于删点就等于在时间上退到父亲，然后之后就在父亲的基础下再加点。

如果可以离线那么我们树剖维护，but在线那么改成LCT就可以了。

题目

参考博客

#include 

using namespace std;
int MOD;
int ad(int x, int y) {
    x += y;
    return x >= MOD ? x - MOD : x;
}
int mu(int x, int y) { return 1ll * x * y % MOD; }
const int maxn = 3e5 + 5;

int ch[maxn][2], fa[maxn], fa_tru[maxn]; // lct fa actually fa
int sm[maxn], tot, A[maxn], rev[maxn], dep[maxn], lz[maxn];
vector> BC[maxn];
static bool isroot(int p) { return ch[fa[p]][0] != p && ch[fa[p]][1] != p; }
void putup(int p) { sm[p] = ad(ad(sm[ch[p][0]], sm[ch[p][1]]), A[p]); }
void rotate(int x) {
    int y = fa[x];
    int z = fa[y];
    fa[x] = z;
    if (!isroot(y)) {
        ch[z][ch[z][1] == y] = x;
    }
    int k = (ch[y][1] == x);
    ch[y][k] = ch[x][k ^ 1];
    fa[ch[y][k]] = y;
    fa[y] = x;
    ch[x][k ^ 1] = y;
    putup(y);
    putup(x);
}
void pushdown(int p) {
    if (rev[p]) {
        swap(ch[p][0], ch[p][1]);
        rev[ch[p][0]] ^= 1, rev[ch[p][1]] ^= 1;
        rev[p] = 0;
    }
    if (lz[p] != 1) {
        A[ch[p][0]] = mu(A[ch[p][0]], lz[p]);
        A[ch[p][1]] = mu(A[ch[p][1]], lz[p]);
        sm[ch[p][0]] = mu(sm[ch[p][0]], lz[p]);
        sm[ch[p][1]] = mu(sm[ch[p][1]], lz[p]);
        lz[ch[p][0]] = mu(lz[ch[p][0]], lz[p]);
        lz[ch[p][1]] = mu(lz[ch[p][1]], lz[p]);
        lz[p] = 1;
    }
}
void splay(int x) {
    int y, z;
    static int sta[maxn], top;
    top = 0;
    sta[++top] = x;
    for (int i = x; !isroot(i); i = fa[i]) {
        sta[++top] = fa[i];
    }
    while (top)
        pushdown(sta[top--]);
    while (!isroot(x)) {
        y = fa[x];
        z = fa[y];
        if (!isroot(y))
            (ch[z][0] == y) ^ (ch[y][0] == x) ? rotate(x) : rotate(y);
        rotate(x);
    }
}
void acc(int x) {
    for (int y = 0; x; y = x, x = fa[x]) {
        splay(x);
        ch[x][1] = y;
        putup(x);
    }
}
void setroot(int x) {
    acc(x);
    splay(x);
    rev[x] ^= 1;
}
void link(int x, int y) {
    setroot(x);
    fa[x] = y;
}
int getp(int tim, int rank) {
    auto it = --upper_bound(BC[rank].begin(), BC[rank].end(),
                            make_pair(tim, 0x3f3f3f3f));
    return it->second;
}
int M, T, NOW, LA;
int main() {
    scanf("%d%d%d", &M, &MOD, &T);
    int OPT, S, L, R, Y;
    for (int tim = 1; tim <= M; tim++) {
        scanf("%d%d", &OPT, &S);
        if (OPT == 1) {
            if (T)
                S = (S ^ LA);
            if (S == 0) {
                NOW = fa_tru[NOW];
            } else {
                ++tot;
                lz[tot] = 1;
                fa_tru[tot] = fa[tot] = NOW;
                dep[tot] = dep[NOW] + 1;
                BC[dep[tot]].push_back(make_pair(tim, tot));
                A[tot] = sm[tot] = S;
                NOW = tot;
            }
        } else if (OPT == 2) {
            scanf("%d%d%d", &L, &R, &Y);
            if (T)
                Y = Y ^ LA;
            L = getp(S, L); // S 天 第L名
            R = getp(S, R);
            setroot(L);
            acc(R);
            splay(R);
            A[R] = mu(A[R], Y);
            sm[R] = mu(sm[R], Y);
            lz[R] = mu(lz[R], Y);
        } else {
            scanf("%d%d", &L, &R);
            L = getp(S, L);
            R = getp(S, R);
            setroot(L), acc(R), splay(R);
            LA = sm[R];
            printf("%d\n", LA);
        }
    }
    return 0;
}