[SDOI2013]森林

迈不过友情╰ 2021-12-23 07:49 190阅读 0赞

**主席树**  
离散化后  
每个点储存从根到它的路径上的点权  
新加边时直接用**启发式合并**，直接把size小的重构  
询问时sum\[u\]+sum\[v\]-sum\[lca\]-sum\[fa\[lca\]\]来比较，在树上二分  
LCA用倍增求，在**启发式合并**时**暴力**更新  
连通性用并查集维护，再维护每个联通快的size  
空间开大点就可以过了

# include <bits/stdc++.h>
    # define IL inline
    # define RG register
    # define Fill(a, b) memset(a, b, sizeof(a))
    using namespace std;
    typedef long long ll;
    const int _(2e5 + 10), __(1e7 + 10);
    
    IL ll Read(){
        RG char c = getchar(); RG ll x = 0, z = 1;
        for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
        for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
        return x * z;
    }
    
    int n, m, len, w[_], fst[_], nxt[_], to[_], cnt, deep[_], id[_], fa[17][_], ls[__], rs[__], sz[__], rt[__], num, Fa[_], size[_];
    
    IL void Add(RG int u, RG int v){  to[cnt] = v; nxt[cnt] = fst[u]; fst[u] = cnt++;  }
    
    IL void Build(RG int &x, RG int l, RG int r){
        x = ++num; if(l == r) return;
        RG int mid = (l + r) >> 1;
        Build(ls[x], l, mid); Build(rs[x], mid + 1, r);
    }
    
    IL void Modify(RG int &x, RG int l, RG int r, RG int val){
        sz[++num] = sz[x]; ls[num] = ls[x]; rs[num] = rs[x];
        sz[x = num]++;
        if(l == r) return;
        RG int mid = (l + r) >> 1;
        if(val <= mid) Modify(ls[x], l, mid, val);
        else Modify(rs[x], mid + 1, r, val);
    }
    
    IL int Query(RG int A, RG int B, RG int C, RG int D, RG int l, RG int r, RG int k){
        if(l == r) return l;
        RG int sum = sz[ls[A]] + sz[ls[B]] - sz[ls[C]] - sz[ls[D]], mid = (l + r) >> 1;
        if(sum >= k) return Query(ls[A], ls[B], ls[C], ls[D], l, mid, k);
        else return Query(rs[A], rs[B], rs[C], rs[D], mid + 1, r, k - sum);
    }
    
    IL void Dfs(RG int u, RG int Fa){
        deep[u] = deep[Fa] + 1; fa[0][u] = Fa;
        for(RG int j = 1; j <= 16; j++) fa[j][u] = fa[j - 1][fa[j - 1][u]];
        rt[u] = rt[Fa]; Modify(rt[u], 1, len, id[u]);
        for(RG int e = fst[u]; e != -1; e = nxt[e]) if(to[e] != Fa) Dfs(to[e], u);
    }
    
    IL int LCA(RG int x, RG int y){
        if(deep[x] < deep[y]) swap(x, y);
        for(RG int j = 16; j >= 0; j--) if(deep[fa[j][x]] >= deep[y]) x = fa[j][x];
        if(x == y) return x;
        for(RG int j = 16; j >= 0; j--) if(fa[j][x] != fa[j][y]) x = fa[j][x], y = fa[j][y];
        return fa[0][x];
    }
    
    IL int Find(RG int x){  return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);  }
    
    int main(RG int argc, RG char* argv[]){
        Read(); n = Read(); m = Read(); RG int T = Read(), ans = 0, x, y, k; num = cnt = 0;
        for(RG int i = 1; i <= n; i++) id[i] = w[i] = Read(), Fa[i] = i, size[i] = 1, fst[i] = -1;
        sort(w + 1, w + n + 1); len = unique(w + 1, w + n + 1) - w - 1;
        for(RG int i = 1; i <= n; i++) id[i] = lower_bound(w + 1, w + len + 1, id[i]) - w;
        for(RG int i = 1, u, v; i <= m; i++){
            u = Read(), v = Read(), Add(u, v), Add(v, u);
            RG int fx = Find(u), fy = Find(v);
            Fa[fx] = fy; size[fy] += size[fx];
        }
        Build(rt[0], 1, len);
        for(RG int i = 1; i <= n; i++) if(!deep[i]) Dfs(i, 0);
        while(T--){
            RG char c; scanf(" %c", &c);
            x = Read() ^ ans; y = Read() ^ ans;
            if(c == 'L'){
                RG int fx = Find(x), fy = Find(y);
                if(size[fx] < size[fy]) swap(x, y);
                Dfs(y, x);
                Fa[fx] = fy; size[fy] += size[fx];
                Add(x, y); Add(y, x);
            }
            else{
                k = Read() ^ ans; RG int lca = LCA(x, y);
                ans = w[Query(rt[x], rt[y], rt[lca], rt[fa[0][lca]], 1, len, k)];
                printf("%d\n", ans);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/cjoieryl/p/8206365.html