51nod1648 洞 LCT

非常简单的一眼LCT，然而我没有在20min内码完，太失败了...

第一问，直接查根的前驱

第二问，查链的子树大小

复杂度$O((n + m) log n)$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

extern inline char gc() {
    static char RR[23456], *S = RR + 23333, *T = RR + 23333;
    if(S == T) fread(RR, 1, 23333, stdin), S = RR;
    return *S ++;
}
inline int read() {
    int p = 0, w = 1; char c = gc();
    while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
    while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
    return p * w;
}

int wr[50], rw;
#define pc(o) *W ++ = (o)
char WR[30000005], *W = WR;
inline void write(int x, char c) {
    if(!x) pc('0');
    if(x < 0) x = -x, pc('-');
    while(x) wr[++ rw] = x % 10, x /= 10;
    while(rw) pc(wr[rw --] + '0'); pc(c);
}

#define ri register int
#define sid 200500

#define ls(o) s[o][0]
#define rs(o) s[o][1]
int n, m, a[sid];
int fa[sid], s[sid][2], rev[sid], sz[sid]; 

inline bool isr(int o) { return ls(fa[o]) != o && rs(fa[o]) != o; }
inline bool isrc(int o) { return rs(fa[o]) == o; }
inline void upd(int o) { sz[o] = sz[ls(o)] + sz[rs(o)] + 1; }

inline void rotate(int o) {
    int f = fa[o], g = fa[f];
    int ro = isrc(o), rf = isrc(f);
    fa[o] = g; if(!isr(f)) s[g][rf] = o;
    if(s[o][ro ^ 1]) fa[s[o][ro ^ 1]] = f;
    s[f][ro] = s[o][ro ^ 1]; fa[f] = o; s[o][ro ^ 1] = f;
    upd(f); upd(o);
}

inline void prev(int o) { 
    swap(ls(o), rs(o)); 
    rev[o] ^= 1; 
}

inline void prv(int o) {
    if(!rev[o]) return;
    prev(ls(o)); prev(rs(o)); rev[o] = 0;
}

inline void pushrev(int o) { 
    if(!isr(o)) pushrev(fa[o]); 
    prv(o);
}

void splay(int o) {
    pushrev(o);
    while(!isr(o)) {
        int f = fa[o];
        if(!isr(f)) rotate(isrc(o) == isrc(f) ? f : o); 
        rotate(o);
    }
}

void access(int o) {
    for(ri t = 0; o; t = o, o = fa[o])
    splay(o), s[o][1] = t, upd(o);
}

inline void makeroot(int o) { 
    access(o); splay(o); prev(o); 
}

inline void link(int u, int v) { 
    makeroot(u); fa[u] = v; 
}

inline void cut(int u, int v) { 
    makeroot(u); access(v); splay(v);
    s[v][0] = 0; fa[u] = 0; upd(v);
}

inline int get(int u) { 
    prv(u); u = s[u][1]; prv(u);
    while(s[u][0]) u = s[u][0], prv(u); 
    return u; 
}

inline void qry(int u) {
    makeroot(n + 1); access(u); splay(n + 1);
    int ans2 = sz[n + 1] - 1, ans1 = get(n + 1);
    splay(ans1); write(ans1, ' '); write(ans2, '
');
}

int main() {
    n = read(); m = read();
    for(ri i = 1; i <= n; i ++) {
        a[i] = read();
        if(i + a[i] <= n) link(i, i + a[i]);
        else link(i, n + 1);
    }
    for(ri i = 1; i <= m; i ++) {
        int opt = read(), x = read();
        if(opt == 0) { 
            if(x + a[x] <= n) cut(x, x + a[x]); else cut(x, n + 1); int y = read();
            a[x] = y; if(x + a[x] <= n) link(x, x + a[x]); else link(x, n + 1);
        } else qry(x);
    }
    fwrite(WR, 1, W - WR, stdout);
    return 0;
}