BZOJ 3123 「SDOI2013」森林

这题……半年前写了没调出来……

首先不考虑第一个操作，这不就是「Count on a Tree」？
沿用之前的想法，把路径信息转化为到根的路径信息相减。

那么考虑连边，即合并。
于是——
启（大）发（力）式 合 并！

首先用 dsu 找根，然后在合并的时候先判大小，把小的接到大的上去，均摊分析下最多合并 O(logn) 次。
然后 DFS 更新重儿子和重链顶（是的没错我用树剖做 LCA）以及主席树。

树剖常数还是比 LCT 和倍增小很多的……
目前 BZOJ 第三优解。

代码：

#include <cstdio>
#include <algorithm>
#define ls(p) seg[p].ls
#define rs(p) seg[p].rs
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 8e4;
int n,m,t,lastans;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
int a[N + 5],ind[N + 5],len;
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v;
    pre[tot] = first[u];
    first[u] = tot;
}
struct node
{
    int sum;
    int ls,rs;
} seg[(N << 7) + 10];
void insert(int x,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],p = tot,++seg[p].sum;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,ls(p),tl,mid) : insert(x,rs(p),mid + 1,tr);
}
int query(int k,int x,int y,int lca,int fa_lca,int tl,int tr)
{
    if(tl == tr)
        return tl;
    int sum = seg[ls(x)].sum + seg[ls(y)].sum - seg[ls(lca)].sum - seg[ls(fa_lca)].sum;
    int mid = tl + tr >> 1;
    if(k <= sum)
        return query(k,ls(x),ls(y),ls(lca),ls(fa_lca),tl,mid);
    else
        return query(k - sum,rs(x),rs(y),rs(lca),rs(fa_lca),mid + 1,tr);
}
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],fat[N + 5];
inline int get(int x)
{
    return !fat[x] ? x : fat[x] = get(fat[x]);
}
int rt[N + 5];
void dfs(int p)
{
    insert(a[p],rt[p] = rt[fa[p]],1,len);
    sz[p] = 1,son[p] = 0;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = fat[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs(to[i]),sz[p] += sz[to[i]];
            if(!son[p] || sz[to[i]] > sz[son[p]])
                son[p] = to[i];
        }
}
void get_top(int p)
{
    if(son[p])
        top[son[p]] = top[p],get_top(son[p]);
    for(register int i = first[p];i;i = pre[i])
        if((to[i] ^ fa[p]) && (to[i] ^ son[p]))
            top[to[i]] = to[i],get_top(to[i]);
}
inline void link(int u,int v)
{
    add(u,v),add(v,u);
    if(sz[get(u)] < sz[get(v)])
        swap(u,v);
    fa[v] = fat[v] = u,dep[v] = dep[u] + 1,dfs(v),top[v] = v,get_top(v);
}
inline int getlca(int x,int y)
{
    while(top[x] ^ top[y])
        dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
    return dep[x] < dep[y] ? x : y;
}
int main()
{
    read(n),read(n),read(m),read(t);
    for(register int i = 1;i <= n;++i)
        read(a[i]),ind[i] = a[i];
    sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
    for(register int i = 1;i <= n;++i)
        a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
    int u,v;
    while(m--)
        read(u),read(v),add(u,v),add(v,u);
    for(register int i = 1;i <= n;++i)
        if(!fa[i])
            dep[i] = 1,dfs(i),top[i] = i,get_top(i);
    char op;
    int x,y,k;
    while(t--)
    {
        op = 0;
        while(op < 'A' || op > 'Z')
            op = gc();
        if(op == 'Q')
        {
            read(x),read(y),read(k),x ^= lastans,y ^= lastans,k ^= lastans;
            int lca = getlca(x,y);
            printf("%d\n",lastans = ind[query(k,rt[x],rt[y],rt[lca],rt[fa[lca]],1,len)]);
        }
        else
            read(x),read(y),link(x ^= lastans,y ^= lastans);
    }
}