上手

参考

我写的东西都是为了补充这些资料,所以先浏览下这些 :

QTREE解法的一些研究 - Yang Zhe 一个论文,自己搜吧
Kuangbin 写的这个模板题的代码
语言还挺生动的。。
Yang Zhe 论文注解版

然后。。如果你发现你学不会。。就看代码。。就能学会了。。。

改造 Splay

哎。。感觉真的没什么讲的,主要是 access 的实现还有 rot 和 fa 的变异。
access 大家都能看懂了。。

fa 和 splay 里的 fa 不一样了。一颗 splay 的根也可以有 fa,代表这棵 splay 维护的路径的最上端节点的fa。(这样做的主要原因是方便access)
原来我们认为一个节点没有 fa 就是根,现在都有 fa 了怎么办呢?就再开一个bool rt[]表示它是不是根
为了区别和 splay 的不同,我把 fa 改叫 pre 了
然后我们需要 splay 里的代码 把判根的方法从 fa[]是否空 改到 rt[]真假 (这点主要影响splay函数),还要维护新fa的性质。

旋转

举个例子,rot

inline void rot(int o) {
    int d = gd(o), x = pre[o];
  //这段是把 o 替换到 x 原来的位置
    pre[o] = pre[x];//不管 x 是不是根,它的父亲都将成为 o 的父亲
    if (rt[x]) rt[x] = 0, rt[o] = 1; //如果 x 是根,就不改 pre[x] 的儿子,因为 ch[pre[x]][0/1] 都不是 x,因为他们都不在一颗 splay 里
    else ch[pre[x]][gd(x)] = o; //x 不是根,按普通 splay 一样连下
  //处理孩子之类的
    lk(ch[o][d^1], x, d);
    lk(x, o, d^1);
    up(x);
    up(o);
}

splay

除了到达根的条件,其他不变。

从子节点更新

然后你懂的,splay 一般要 up。
up 的时机?
Splay 的结构改变的时候。
实际上只存在一种情况, Splay 的结构会改动:ch[] 改动的时候。
也就是 ch[]改动 <-当且仅当-> 调用 up

为什么pre[]和up没这种关系我就不证了。如果理解lct的话就明白,不理解的话我解释一下这点反而会更迷?

然后写的时候注意下改ch[]就要up就行, 也就是accees,cut和传统项目splay。

access

没啥难懂的。自己去看 kuangbin 代码吧。注意access里的每次pre都是跳到上一个链而不是在splay中移动就行。

维护边

把边也转化成点,见水管局长

代码

通过抄标程学算法(逃
这种比较复杂的数据结构啊,说说真的是没啥用,详细描述过程也没用,还是看代码和写代码吧。
就像 splay 这种东西,没什么可讲的,就是看谁写的比较精妙。

魔鬼在细节中

Prob Hint
2049 SDOI2008 Cave洞穴勘探 摸鱼
3091 城市旅行 本来早上起来想写道裸题休闲一下,结果随机抽中了一道数学期望…不会数学期望就去搜题解题解2
2631-Tree md卡常,lltle,用uint能过
3282-Tree 休闲
2157-旅游 明明是树剖题。不过可以用lct做,试下把边转换成点的技巧。我没仔细看题以为有link-cut操作才写的树剖
水管局长 瓶颈居然是找边……排序lowerbound, 注意uv定序
1180-CROATIAN2009-OTOCI 淼淼淼,安慰自己今天不是特别颓废,至少膜chad学了不存rt的写法对吧?。。。顺便把自己的lct压到最短
//1180-OTOCI
#include <cstdio>
#include <algorithm>
const int N = 3e4 + 10;
int n, m, pre[N], ch[N][2], w[N], s[N];
bool rev[N];
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
    if (x) pre[x] = y;
    if (y) ch[y][d] = x;
}
inline bool rt(int o) {return ch[pre[o]][gd(o)] != o;}
inline void mkr(int o) {if (o) std::swap(ch[o][1], ch[o][0]), rev[o] ^= 1;}
inline void down(int o) {if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;}
inline void up(int o) {
    s[o] = w[o] + s[ch[o][0]] + s[ch[o][1]];
}
inline void rot(int o) {
    int x = pre[o], d = gd(o);
    pre[o] = pre[x];
    if (!rt(x)) ch[pre[x]][gd(x)] = o;
    lk(ch[o][d^1], x, d);
    lk(x, o, d^1);
    up(x), up(o);
}
void clear(int o) {
    if (!rt(o)) clear(pre[o]);
    down(o);
}
inline void splay(int o) {
    for (clear(o); !rt(o); rot(o))
        if (!rt(pre[o])) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
    for (int x = 0; o; o = pre[x = o])
        splay(o), ch[o][1] = x, up(o);
}
inline void mkrt(int o) {access(o), splay(o), mkr(o);}
int find(int o) {return pre[o] ? find(pre[o]) : o;}
inline void link(int u, int v){mkrt(u),pre[u] = v;}
char cmd[20];
int main() {
//    freopen("input", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", w + i), up(i);
    scanf("%d", &m);
    while (m--) {
        int u, v;
        scanf("%s%d%d", cmd, &u, &v);
        if (cmd[0] == 'b') {
            if (find(u) == find(v)) puts("no");
            else {
                puts("yes");
                link(u, v);
            }
        }
        else if (cmd[0] == 'p') splay(u), w[u] = v, up(u);
        else if (cmd[0] == 'e') {
            if (find(u) == find(v)) {
                mkrt(u), access(v), splay(v);
                printf("%d\n", s[v]);
            }
            else puts("impossible");
        }
    }
}
//2049-SDOI2008-Cave
#include <cstdio>
#include <algorithm>
#include <cassert>
#define file(x) "sdoi2008_cave." #x
const int N = 1e4 + 10;
int n, m, pre[N], ch[N][2];
bool rt[N], rev[N];
char cmd[20];
inline void mkr(int o) {
    if (!o) return;
    rev[o] ^= 1;
    std::swap(ch[o][0], ch[o][1]);
}
inline void down(int o) {
    if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
    if (x) pre[x] = y;
    if (y) ch[y][d] = x;
}
inline void rot(int o) {
    int d = gd(o), x = pre[o];
    if (rt[x]) pre[o] = pre[x], rt[x] = 0, rt[o] = 1;
    else lk(o, pre[x], gd(x));
    lk(ch[o][d^1], x, d);
    lk(x, o, d^1);
//    up(x), up(o);
}
void clear(int o) {
    if (!rt[o]) clear(pre[o]);
    down(o);
}
void splay(int o) {
    for (clear(o); !rt[o]; rot(o))
        if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
void access(int o) {
    for (int x = 0; o;) {
        splay(o);
        rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
        o = pre[x = o];
    }
}
inline void mkrt(int o) {
    access(o);
    splay(o);
    mkr(o);
}
inline void cut(int u, int v) {
    mkrt(u);
    access(v);
    splay(v);
    pre[ch[v][0]] = pre[v], rt[ch[v][0]] = 1;
    pre[v] = ch[v][0] = 0;
}
inline void link(int u, int v) {
    mkrt(u);
    pre[u] = v;
}
inline bool query(int u, int v) {
    while (pre[u]) u = pre[u];
    while (pre[v]) v = pre[v];
    return u == v;
}
int main() {
//    freopen(file(in), "r", stdin);
//    freopen(file(out), "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) rt[i] = 1;
    while (m--) {
        int x, y;
        scanf("%s%d%d", cmd, &x, &y);
        if (cmd[0] == 'Q') puts(query(x, y) ? "Yes" : "No");
        else if (cmd[0] == 'C') link(x, y);
        else cut(x, y);
    }
}
//3091 城市旅行
#include <cstdio>
#include <algorithm>
#include <vector>
const int N = 5e4 + 10;
typedef long long ll;
int n, m, pre[N], ch[N][2];
bool rt[N], rev[N];
ll ad[N], w[N], s[N], sz[N], ls[N], rs[N], e[N];
inline void up(int o) {
    s[o] = w[o] + s[ch[o][0]] + s[ch[o][1]];
    sz[o] = 1 + sz[ch[o][0]] + sz[ch[o][1]];
    ls[o] = ls[ch[o][0]] + (sz[ch[o][0]] + 1)*s[ch[o][1]] + ls[ch[o][1]] + w[o]*(sz[ch[o][0]] + 1);
    rs[o] = rs[ch[o][1]] + (sz[ch[o][1]] + 1)*s[ch[o][0]] + rs[ch[o][0]] + w[o]*(sz[ch[o][1]] + 1);
    e[o] = e[ch[o][0]] + e[ch[o][1]] + (sz[ch[o][0]] + 1)*rs[ch[o][1]] + (sz[ch[o][1]] + 1)*ls[ch[o][0]] + (sz[ch[o][0]] + 1)*(sz[ch[o][1]] + 1)*w[o];
}
inline void mkad(int o, ll x) {
    if (o)  {
        s[o] += x*sz[o],
        w[o] += x,
        ad[o] += x;
        ll u = sz[o]*(sz[o] + 1)*x/2;
        ls[o] += u, rs[o] += u;
        e[o] += x*sz[o]*(sz[o] + 1)*(sz[o] + 2)/6;
    }
}
inline void mkr(int o) {if (o) std::swap(ch[o][0], ch[o][1]), std::swap(ls[o], rs[o]), rev[o] ^= 1;}
inline void down(int o) {
    if (ad[o]) mkad(ch[o][0], ad[o]), mkad(ch[o][1], ad[o]), ad[o] = 0;
    if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
    if (x) pre[x] = y;
    if (y) ch[y][d] = x;
}
inline void rot(int o) {
    int d = gd(o), x = pre[o];
    pre[o] = pre[x];
    if (rt[x]) rt[x] = 0, rt[o] = 1;
    else ch[pre[x]][gd(x)] = o;
    lk(ch[o][d^1], x, d);
    lk(x, o, d^1);
    up(x);
    up(o);
}
inline void clear(int o) {
    if (!rt[o]) clear(pre[o]);
    down(o);
}
inline void splay(int o) {
    for (clear(o); !rt[o]; rot(o))
        if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
    for (int x = 0; o; ) {
        splay(o);
        rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
        up(o);
        o = pre[x = o];
    }
}
inline void mkrt(int o) {
    access(o);
    splay(o);
    mkr(o);
}
inline int find(int u) {for(;pre[u]; u = pre[u]); return u;}
inline void cut(int u, int v) {
    if (find(u) != find(v)) return;
    mkrt(u);
    access(v);
    splay(v);
    if (ch[v][0] == u && ch[u][1] == 0) {
        pre[ch[v][0]] = pre[v], rt[ch[v][0]] = 1;
        pre[v] = ch[v][0] = 0;
        up(v);
    }
}
inline void link(int u, int v) {
    if (find(u) == find(v)) return;
    mkrt(u);
    pre[u] = v;
}
ll gcd(ll a, ll b) {return b ? gcd(b, a%b) : a;}
std::vector<int> to[N];
void dfs(int u, int fa) {
    for (int i = 0; i < (int)to[u].size(); i++) if (to[u][i] != fa) pre[to[u][i]] = u, dfs(to[u][i], u);
}
int main() {
//    freopen("input", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", w + i), rt[i] = 1, up(i);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        to[u].push_back(v);
        to[v].push_back(u);
    }
    dfs(1, 0);
    while (m--) {
        int t, u, v;
        scanf("%d%d%d", &t, &u, &v);
        if (t == 1) cut(u, v);
        else if (t == 2) link(u, v);
        else if (t == 3) {
            int d;
            scanf("%d", &d);
            if (find(u) != find(v)) continue;
            mkrt(u);
            access(v);
            splay(v);
            mkad(v, d);
        }
        else {
            if (find(u) != find(v)) {
                puts("-1");
                continue;
            }
            mkrt(u);
            access(v);
            splay(v);
            ll c = e[v], m = sz[v]*(sz[v] + 1)/2, d = gcd(c, m);
            printf("%lld/%lld\n", c/d, m/d);
        }
    }
}
//2631-tree
#include <cstdio>
#include <vector>
#include <algorithm>
typedef unsigned int ll;
const int N = 1e5 + 10;
const ll M = 51061;
std::vector<int> to[N];
int n, m, pre[N], ch[N][2];
ll sz[N], ad[N], mu[N], w[N], s[N];
bool rt[N], rev[N];
void dfs(int u, int fa) {
    pre[u] = fa;
    for (int i = 0; i < (int)to[u].size(); i++) if (to[u][i] != fa) dfs(to[u][i], u);
}
inline void up(int o) {
    sz[o] = 1 + sz[ch[o][0]] + sz[ch[o][1]];
    s[o] = (w[o] + s[ch[o][0]] + s[ch[o][1]])%M;
}
inline void mkr(int o) {
    rev[o] ^= 1, std::swap(ch[o][0], ch[o][1]);
}
inline void mkad(int o, ll x) {
    if (o) {
        s[o] = (s[o] + sz[o]*x)%M;
        w[o] = (w[o] + x)%M;
        ad[o] = (ad[o] + x)%M;
    }
}
inline void mkmu(int o, ll x) {
    if (o) {
        s[o] = x*s[o]%M;
        w[o] = x*w[o]%M;
        ad[o] = ad[o]*x%M;
        mu[o] = mu[o]*x%M;
    }
}
inline void down(int o) {
    if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;
    if (mu[o] != 1) mkmu(ch[o][0], mu[o]), mkmu(ch[o][1], mu[o]), mu[o] = 1;
    if (ad[o]) mkad(ch[o][0], ad[o]), mkad(ch[o][1], ad[o]), ad[o] = 0;
}
inline void lk(int x, int y, int d) {
    if (x) pre[x] = y;
    if (y) ch[y][d] = x;
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void rot(int o) {
    int x = pre[o], d = gd(o);
    pre[o] = pre[x];
    if (rt[x]) rt[x] = 0, rt[o] = 1;
    else ch[pre[x]][gd(x)] = o;
    lk(ch[o][d^1], x, d);
    lk(x, o, d^1);
    up(x);
    up(o);
}
void clear(int o) {
    if (!rt[o]) clear(pre[o]);
    down(o);
}
inline void splay(int o) {
    for (clear(o); !rt[o]; rot(o))
        if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
    for (int x = 0; o;) {
        splay(o);
        rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
        up(o);
        o = pre[x = o];
    }
}
inline void mkrt(int u) {
    access(u);
    splay(u);
    mkr(u);
}
inline void link(int u, int v) {
    mkrt(u);
    pre[u] = v;
}
inline void cut(int u, int v) {
    mkrt(u);
    access(v);
    splay(v);
    pre[ch[v][0]] = pre[v], rt[ch[v][0]] = 1;
    pre[v] = ch[v][0] = 0;
    up(v);
}
inline void select(int u, int v) {
    mkrt(u);
    access(v);
    splay(v);
}
char cmd[5];
int main() {
//    freopen("input", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        rt[i] = w[i] = mu[i] = 1;
        up(i);
        int u, v;scanf("%d%d", &u ,&v);
        to[u].push_back(v);
        to[v].push_back(u);
    }
    rt[n] = w[n] = mu[n] = 1;
    up(n);
    dfs(1, 0);
    while (m--) {
        int u0, v0, c, u1, v1;
        scanf("%s%d%d", cmd, &u0, &v0);
        if (cmd[0] == '+') {
            scanf("%d", &c);
            select(u0, v0);
            mkad(v0, c);
        }
        else if (cmd[0] == '-') {
            scanf("%d%d", &u1, &v1);
            cut(u0, v0);
            link(u1, v1);
        }
        else if (cmd[0] == '*') {
            scanf("%d", &c);
            select(u0, v0);
            mkmu(v0, c);
        }
        else if (cmd[0] == '/') {
            select(u0, v0);
            printf("%u\n", s[v0]);
        }
    }
}
//水管局长
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <map>
#define file(x) "tube."#x
#define f(x) re
typedef long long ll;
const int M = 1e6 + 10, N = 1e5 +10 +M, Q = 1e5 + 10, V = 1e5 + 10;
namespace I {
    const int L = 1 << 15 | 1;
    char *s,*t, buf[L];
    inline char gc() {
        if (s == t) t = (s = buf) + fread(buf, 1, L, stdin);
        return *s++;
    }
    inline int gi() {
        int ch = gc(), x = 0;
        while (!isdigit(ch)) ch = gc();
        while (isdigit(ch)) x = x*10 + ch - '0', ch = gc();
        return x;
    }
}using I::gi;
int n, m, q, ch[N][2], pre[N], hed[N], nxt[M << 2], w[N], mxi[N], st[M << 2], th[M];
bool rt[N], rev[N];
struct EDGE{int u, v, w;
    bool rm, in;
    bool operator<(const EDGE& b)const {
        return w < b.w;
    }
    inline void rd() {
        u = gi(), v = gi(), w = gi();
    }
}e[M], qu[Q];
bool cmp2(int i, int j) {return e[i].u < e[j].u || (e[i].u == e[j].u && e[i].v < e[j].v);}
inline ll zip(ll u, ll v) {
    if (u > v) std::swap(u, v);
    return u*V + v;
}
inline void _add(int u, int v){
    static int sz = 0;
    st[++sz] = v;
    nxt[sz] = hed[u], hed[u] = sz;
}
inline void add(int u, int v){
    _add(u, v), _add(v, u);
}
namespace Kruskal {
    int p[N];
    int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
    void solve() {
        for (int i = 1; i <= m; i++) p[i] = i;
        std::sort(e + 1, e + 1 + m);
        for (int i = 1; i <= m; i++) if (!e[i].rm) {
            int u = find(e[i].u), v = find(e[i].v);
            if (u == v) continue;
            p[u] = v;
            e[i].in = 1;
        }
    }
}
inline void mkr(int o) {if(o) std::swap(ch[o][0], ch[o][1]), rev[o] ^= 1;}
inline void down(int o) {if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;}
inline void up(int o) {
    mxi[o] = o > n ? o : 0;
    for (int i = 0; i < 2; i++) if (w[mxi[ch[o][i]]] > w[mxi[o]]) mxi[o] = mxi[ch[o][i]];
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
    if (x) pre[x] = y;
    if (y) ch[y][d] = x;
}
//inline bool rt(int o) {return ch[pre[o]][0] == o || ch[pre[o]][1] == o;}
inline void rot(int o) {
    int x = pre[o], d = gd(o);
    pre[o] = pre[x];
    if (rt[x]) rt[x] = 0, rt[o] = 1;
    else ch[pre[x]][gd(x)] = o;
    lk(ch[o][d^1], x, d);
    lk(x, o, d^1);
    up(x);
    up(o);
}
void clear(int o) {
    if (!rt[o]) clear(pre[o]);
    down(o);
}
inline void splay(int o) {
    for (clear(o); !rt[o]; rot(o))
        if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
    for (int x = 0; o; ) {
        splay(o);
        rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
        up(o);
        o = pre[x = o];
    }
}
inline void mkrt(int o) {
    access(o);
    splay(o);
    mkr(o);
}
inline void link(int u, int v) {mkrt(u), pre[u] = v;}
inline void cut(int u, int v) {
    mkrt(u);
    access(v);
    splay(v);
    pre[u] = pre[v], rt[u] = 1;
    pre[v] = ch[v][0] = 0;
    up(v);
}
void dfs(int u, int fa) {
    pre[u] = fa;
    rt[u] = 1;
    up(u);
    for (int g = hed[u], v; v = st[g]; g = nxt[g]) if (v != fa) dfs(v, u);
}
inline int query(int u, int v) {
    mkrt(u),access(v), splay(v);
    return mxi[v];
}
int find(int u, int v) {
    if (u > v) std::swap(u, v);
    e[m + 1].u = u, e[m + 1].v = v;
    int p = std::lower_bound(th + 1, th + 1 + m, m + 1, cmp2) - th;
    return th[p];
}
int main() {
//    freopen("input", "r", stdin);
//    freopen(file(in), "r", stdin);
//    freopen(file(out), "w", stdout);
    n = gi(), m = gi(), q = gi();
    for (int i = 1; i <= m; i++) e[i].rd(), th[i] = i;
    std::sort(th + 1, th + 1 + m, cmp2);
    for (int i = 1; i <= q; i++) {
        qu[i].rd();
        if (qu[i].u == 2) {
            e[find(qu[i].v, qu[i].w)].rm = 1;
        }
    }
    Kruskal::solve();
    std::sort(th + 1, th + 1 + m, cmp2);
    for (int i = 1; i <= m; i++) {
        if (e[i].in) {
            add(e[i].u, n + i);
            add(e[i].v, n + i);
        }
        w[n + i] = e[i].w;
    }
    dfs(1, 0);
    for (int i = q; i; i--) if (qu[i].u == 1) qu[i].v = w[query(qu[i].v, qu[i].w)];
    else {
        int x = query(qu[i].v, qu[i].w), id = find(qu[i].v, qu[i].w);
        if (w[n + id] < w[x]) {
            cut(x, e[x - n].u);
            cut(x, e[x - n].v);
            link(n + id, qu[i].v);
            link(n + id, qu[i].w);
        }
    }
    for (int i = 1; i <= q; i++) if (qu[i].u == 1) printf("%d\n", qu[i].v);
}

后注:
这些代码也有点时间了,有些地方写的很naive,比如水管局长的cut。
推荐阅读第一个代码,不开数组维护rt的版本。简单很多。
然后水管局长的cut可以splayx然后更简单。