第一次……调完……LCT……上来……水一发…… _(:_」∠)_

样例数据一点也不良心的 LCT 模版题……

周四听了一节课之后啃论文。。感觉 Link/cut tree 并不难的样子 = = 于是昨天晚上下定决心开始码 LCT！(۶* ‘ヮ’)۶”

首先。。决定再手写一遍 Splay。。“应该不会出错的” ← flag *1

然后。。换了一种方法写 Splay 旋转操作。。“好像和原来是一样的” ← flag *2

然后 bla bla bla，bla bla bla。。。。。

码完一堆 Syntax error。。改掉之后直接输入样例各种崩溃。。。好不容易正常了。。自己构造数据狂 RE/WA 不止。。。

（凌晨1点）什么鬼啊不玩了不玩了 （╯°□°）╯︵ ┻━┻（哔——）

然后就梦见写 LCT 了 = = 果然是应了 BZOJ 上的 Nickname 么（笑）［ゆめで すぐ あえるね おやすみなさい］

坐在英语课堂上憋了一上午 = =

（下午2点）不想重写。。继续开始调。。不信今天调不出来 > <

首先用洛谷上的并查集乱搞法 Link/cut disjoint-set（大雾）做一个数据生成器

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 10008

int n, m;
int par[MAXN];
void lcdsu_init()
{
    int i;
    for (i = 0; i < n; ++i) par[i] = -1;
}
int lcdsu_root(int u)
{
    while (par[u] != -1) u = par[u];
    return u;
}
void lcdsu_evert(int u)
{
    int v = par[u], t;
    par[u] = -1;
    while (v != -1) {
        t = par[v];
        par[v] = u;
        u = v; v = t;
    }
}
void lcdsu_union(int u, int v)
{
    lcdsu_evert(u);
    lcdsu_evert(v);
    if (rand() & 1) par[u] = v; else par[v] = u;
}
void lcdsu_cut(int u, int v)
{
    if (par[u] == v) par[u] = -1;
    else par[v] = -1;
}

int main()
{
    unsigned int seed = (unsigned)time(NULL);
    fprintf(stderr, "Seed: %u\n", seed);
    srand(seed);

    scanf("%d%d", &n, &m);
    lcdsu_init();
    printf("%d %d\n", n, m);

    int u, v;
    do {
        u = rand() % n; v = rand() % n;
        if (rand() & 1) {
            if (lcdsu_root(u) == lcdsu_root(v)) {
                if (par[u] == v || par[v] == u) {
                    lcdsu_cut(u, v);
                    printf("Destroy %d %d\n", u + 1, v + 1);
                } else {
                    printf("Query %d %d\n", u + 1, v + 1);
                }
            } else {
                lcdsu_union(u, v);
                printf("Connect %d %d\n", u + 1, v + 1);
            }
        } else {
            printf("Query %d %d\n", u + 1, v + 1);
        }
    } while (--m);

    return 0;
}

然后发现好像顺便把题目也做了 (　ﾟдﾟ) 随便改几行交上去然后发现过了。。。然后交到 BZOJ 上也顺利通过了（−＿−；）

/**************************************************************
    Problem: 2049
    User: cyand1317
    Language: C
    Result: Accepted
    Time:808 ms
    Memory:792 kb
****************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
#define MAXN 10008
 
int n, m;
int par[MAXN];
void lcdsu_init()
{
    int i;
    for (i = 0; i < n; ++i) par[i] = -1;
}
int lcdsu_root(int u)
{
    while (par[u] != -1) u = par[u];
    return u;
}
void lcdsu_evert(int u)
{
    int v = par[u], t;
    par[u] = -1;
    while (v != -1) {
        t = par[v];
        par[v] = u;
        u = v; v = t;
    }
}
void lcdsu_union(int u, int v)
{
    lcdsu_evert(u);
    lcdsu_evert(v);
    if (rand() & 1) par[u] = v; else par[v] = u;
}
void lcdsu_cut(int u, int v)
{
    if (par[u] == v) par[u] = -1;
    else par[v] = -1;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    lcdsu_init();
 
    char op[16]; int u, v;
    do {
        scanf("%s%d%d", op, &u, &v); --u; --v;
        switch (op[0]) {
            case 'C': lcdsu_union(u, v); break;
            case 'D': lcdsu_cut(u, v); break;
            case 'Q': puts(lcdsu_root(u) == lcdsu_root(v) ? "Yes" : "No"); break;
        }
    } while (--m);
 
    return 0;
}

好吧。。

不过还是得滚回去写 LCT。。。

Crash 调调调。。调调调。。。终于不 crash 啦！随机一组大数据继续炸。。。

继续调调调。。调调调。。。终于不 crash 啦！另外随机一组大数据继续炸。。。

好像 Splay 写错了 = = 啊不对没有 = = 啊不对好像真的写错了 = =

……

……

最后发现-_-# Splay 旋转的时候没有 push -_-# 导致有时候要断开和右子树的连接，但有时因为延迟反转标记没推下去而切下的实际是左子树。。。

什么鬼啊这也行 ◡ ヽ(`Д´)ﾉ ┻━┻  智障了大半天才发现啊。。。

改掉。。对拍。。好像对了？（怀疑电脑 ing）

随机 max 数据。。。再随机一组。。再随机一组。。。。。。擦 真的对了真的对了！！！！

好激动～～～～！！！！！！

/**************************************************************
    Problem: 2049
    User: cyand1317
    Language: C++
    Result: Accepted
    Time:3920 ms
    Memory:1060 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
static const int MAXN = 10007;
inline void swap(int &a, int &b) { static int t; t = a; a = b; b = t; }
 
struct __spl_node {
    int child[2], parent;
    bool lz_rev;
} t[MAXN];
 
int spl_epoch = 0;
int ppar[MAXN];
inline int spl_newnode(int parent = -1)
{
    int idx = spl_epoch++;
    t[idx].child[0] = t[idx].child[1] = -1;
    t[idx].parent = parent;
    t[idx].lz_rev = false;
    return idx;
}
inline void spl_push(int idx)
{
    if (idx != -1 && t[idx].lz_rev) {
        t[idx].lz_rev = false;
        if (t[idx].child[0] != -1) t[t[idx].child[0]].lz_rev ^= 1;
        if (t[idx].child[1] != -1) t[t[idx].child[1]].lz_rev ^= 1;
        swap(t[idx].child[0], t[idx].child[1]);
    }
    if (idx != -1) {
        if (t[idx].child[0] != -1) ppar[t[idx].child[0]] = ppar[idx];
        if (t[idx].child[1] != -1) ppar[t[idx].child[1]] = ppar[idx];
    }
}
inline void spl_rotate(int i, int d)
{
    int p = t[i].parent, g = t[p].parent;
    t[p].child[d] = t[i].child[1 - d];
    t[t[i].child[1 - d]].parent = p;
    t[i].child[1 - d] = p;
    t[p].parent = i;
    if (g != -1) t[g].child[t[g].child[1] == p] = i;
    t[i].parent = g;
}
inline void spl_zig(int idx) { spl_rotate(idx, 0); }
inline void spl_zag(int idx) { spl_rotate(idx, 1); }
inline void spl_1splay(int idx)
{
    spl_push(idx);
    spl_rotate(idx, t[t[idx].parent].child[1] == idx);
}
inline void spl_2splay(int idx, int under)
{
    int par = t[idx].parent, gpn = t[par].parent;
    spl_push(idx);
    if (gpn == under) spl_1splay(idx);
    else {
        if (t[gpn].child[0] == par) {
            if (t[par].child[0] == idx) { spl_zig(par); spl_zig(idx); }
            else                        { spl_zag(idx); spl_zig(idx); }
        } else {
            if (t[par].child[0] == idx) { spl_zig(idx); spl_zag(idx); }
            else                        { spl_zag(par); spl_zag(idx); }
        }
    }
}
inline void spl_lift(int idx, int under = -1)
{
    static int chain[MAXN];
    int top = 0, u = idx;
    while (u != under) chain[top++] = (u = t[u].parent);
    for (; top >= 0; --top) spl_push(chain[top]);
    while (t[idx].parent != under) spl_2splay(idx, under);
}
inline void spl_cut(int idx, int child_id)
{
    int cld = t[idx].child[child_id];
    if (cld != -1) {
        t[idx].child[child_id] = -1;
        t[cld].parent = -1;
    }
}
inline void spl_link(int idx, int child_id, int cld)
{
    //assert(t[cld].parent == -1);
    //assert(t[idx].child[child_id] == -1);
    t[cld].parent = idx;
    t[idx].child[child_id] = cld;
}
inline int spl_leftmost(int idx, int lift_under = -1)
{
    int cld = idx;
    while (t[cld].child[0] != -1) cld = t[cld].child[0];
    spl_lift(cld, lift_under);
    return cld;
}
 
inline void lct_init(int n)
{
    for (int i = 1; i <= n; ++i) ppar[i] = -1;
}
void lct_access(int u)
{
    spl_lift(u); spl_push(u);
    if (t[u].child[1] != -1) ppar[t[u].child[1]] = u; spl_cut(u, 1);
    u = spl_leftmost(u);
    int v;
    //assert(t[u].parent == -1);
    while ((v = ppar[u]) != -1) {
        spl_lift(v); spl_push(v);
        if (t[v].child[1] != -1) ppar[t[v].child[1]] = v; spl_cut(v, 1);
        //assert(t[u].parent == -1);
        spl_link(v, 1, u);
        u = spl_leftmost(v);
    }
}
void lct_evert(int u)
{
    lct_access(u);
    spl_lift(u);
    t[u].lz_rev ^= 1;
    ppar[u] = -1;
}
int lct_getroot(int u)
{
    int v = u;
    do {
        u = v;
        lct_access(u);
        spl_lift(u);
        u = spl_leftmost(u);
    } while ((v = ppar[u]) != -1);
    return spl_leftmost(u);
}
void lct_link(int u, int v) // u.father := v
{
    lct_evert(u);
    ppar[u] = v;
    lct_access(u);
}
void lct_cut(int u, int v)
{
    lct_evert(u);
    spl_lift(v);
    lct_access(v);
    spl_lift(u);
    spl_push(u);
    if (t[u].child[1] != -1) ppar[t[u].child[1]] = -1; spl_cut(u, 1);
}
 
int n, m;
 
int main()
{
    scanf("%d%d", &n, &m);
    spl_newnode(-1);
    for (int i = 0; i < n; ++i) spl_newnode(-1); //assert(spl_newnode(i + 1) == i + 1);
    lct_init(n);
 
    char op[16];
    int u, v;
    do {
        scanf("%s%d%d", op, &u, &v);
        switch (op[0]) {
            case 'Q': puts(lct_getroot(u) == lct_getroot(v) ? "Yes" : "No"); break;
            case 'C': lct_link(u, v); break;
            case 'D': lct_cut(u, v); break;
            default: break;
        }
    } while (--m);
 
    return 0;
}

（像窝这样代码长度上天的。。居然只写了 5 KB 不到。。手动鼓掌）（然而如此之乱）

感觉洛谷好像被卡出 bug 了。。。奥妙重重

（is-programmer 似乎发抽了。。屏幕截图：“通过该测试点”×10 以及 “Unaccepted，40 分”） 在这里围观 bug~

好吧总算是又填平了一个大坑 (๑˃̵ᴗ˂̵)و

今天是切不动题了 (/_ ;) 窝需要静静