Fork me on GitHub

「BZOJ3123 / SDOI2013」 森林 主席树+DSU ON TREE

发表于 | 分类于 ，
字数统计: 1,337字 | 阅读时长 ≈ 8分钟

写毒瘤 学套路 .

Links there:BZOJ3123

题意

有一个 $N$ 结点的森林 每一个结点有一个非负权值 初始的时候有 $M$ 条边. 有 $T$ 个操作.

请支持下面两个操作 强制在线

1 $Q$ $x$ $y$ $k$ 查询点 $x$ 到点 $y$ 上第 $k$ 小的权值 保证输入合法

2 $L$ $x$ $y$ 在 $x$ 和 $y$ 之间连边 连完边后保证还是森林.

$N,M,T \leq 80000$

思路

先对于所有出现的值离散化

对于第一个操作考虑对每个联通块开一个主席树每次新加结点就继承$father$的信息.

每次查询的时候在 $x$ $y$ $lca(x,y)$ $fa(lca(x,y))$ 上跑二分

这样的复杂度是 $O(nlog^2n)$ 的.

对于第二个操作来说 这种只有连边没有断边 用 $Link CutTree$ 可以做到 $nlogn$ 但显然给自己加大了代码复杂度 我们考虑启发式合并 记录每个联通块的 $fa$ 和 $size$ 每次连边的时候用并查集去查哪个联通快的 $size$ 更大然后暴力重新计算 $ST$ 表即可 这样的复杂度也是 $O(nlog^2n)$ 的.

总复杂度 $O(nlog^2n)$ 可以垃圾回收但没必要.

Code(人丑代码长)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//What is broken can be reforged. --Riven
#include<bits/stdc++.h>
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define mp make_pair
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
inline char NextChar(void){char c;for(c=getchar();!isalpha(c);c=getchar()); return c;}
const int MAXN = 8e4 + 100;
const int MAXNODE = 1e7 + 100;
int root[MAXN],lson[MAXNODE],rson[MAXNODE],sz[MAXNODE],n,m,T,fa[MAXN],k=0;
int head[MAXN],cnt = 0,cntt = 0,st[MAXN][20],a[MAXN],b[MAXN],sum[MAXN],dep[MAXN],vis[MAXN],nn;
vector<int>lt[MAXN];
inline void addedge(int u,int v){lt[u].pb(v);}

inline int Getid(int x){return lower_bound(b+1,b+nn+1,x)-b;}
inline int getf(int x){return x == fa[x] ? x : fa[x] = getf(fa[x]);}
queue<int>dustbin;

inline int Newnode(){
    if (dustbin.empty()) return ++cnt;
    else {
        int u = dustbin.front();
        dustbin.pop();
        return u;
    }
}
inline void Dec(int u){
    lson[u] = rson[u] = sz[u] = 0;
    dustbin.push(u);
}

inline void decline(int u,int l,int r){
    if (!u) return ;
    if (l != r) {
        int mid = (l + r) >> 1;
        decline(lson[u],l,mid);
        decline(rson[u],mid+1,r);
    }
    Dec(u);
}
inline void build(int &k,int l,int r) {
    k = Newnode();
    sz[k] = 0;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    build(lson[k],l,mid);
    build(rson[k],mid+1,r);
}

inline void ins(int &k,int pre,int l,int r,int x){
    k = Newnode();
    sz[k] = sz[pre] + 1;
    lson[k] = lson[pre]; rson[k] = rson[pre];
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) ins(lson[k],lson[pre],l,mid,x);
    else ins(rson[k],rson[pre],mid+1,r,x);
}

inline int query(int x,int y,int x1,int y1,int l,int r,int k){
    if (l == r) return b[l];
    int mid = (l + r) >> 1;
    int tmp = sz[lson[x]] + sz[lson[y]] - sz[lson[x1]] - sz[lson[y1]];
    if (k <= tmp) return query(lson[x],lson[y],lson[x1],lson[y1],l,mid,k);
    else return query(rson[x],rson[y],rson[x1],rson[y1],mid+1,r,k-tmp);
}

void dfs(int u,int father,int rt){
    ++sum[rt]; st[u][0] = fa[u] = father; dep[u] = dep[father]+1; vis[u] = 1;
    for (int i = 1; i <= 18; ++i)
        st[u][i] = st[st[u][i-1]][i-1];
    //Dec(root[u]);
    root[u] = 0;
    ins(root[u],root[father],1,nn,Getid(a[u]));
    for (int i = 0; i < lt[u].size(); ++i) {
        //printf("%lld\n",v);
        int v = lt[u][i];
        if (v == father) continue;
        dfs(v,u,rt);
    }
}

inline int LCA(int x,int y){
    if (x == y) return x;
    if (dep[x] > dep[y]) swap(x,y);
    for (int i = 18; i >= 0; i--)
        if (dep[st[y][i]] >= dep[x])  y = st[y][i];
    if (x == y) return x;
    for (int i = 18; i >= 0; i--) {
        if (st[x][i] != st[y][i]) {
            x = st[x][i]; y = st[y][i];
        }
    }
    return st[x][0];
}
///------------------head------------------
signed main(signed argc, char *argv[]){
    // freopen("1.in","r",stdin);
    // freopen("1.ans","w",stdout);
    int hjqmy = read();
    hjqmy = 1;T = hjqmy;
    n =  read(),m = read(),T = read();
    rep(i,1,n) {
        b[i] = read();
        a[i] = b[i];
        fa[i] = i;
    }
    sort(b+1,b+n+1);
    nn = unique(b+1,b+n+1)-b-1;
    //rep(i,1,nn) printf("%lld\n",b[i]);
    rep(i,1,m) {
        int x = read(),y = read();
        addedge(x,y);addedge(y,x);
    }
    build(root[0],1,nn);
    for (int i = 1; i <= n; ++i)  if (!vis[i]) dfs(i,0,i),fa[i] = i;
    //for (int i = 1; i <= n; ++i) printf("%lld ",dep[i]);
    //for (int x,y;;) x=read(),y=read(),printf("%lld\n",LCA(x,y));
    int lastans = 0;
    while(T--) {
        char c = NextChar();
        if (c == 'Q') {
            int x = read()^lastans,y = read()^lastans,K = read()^lastans,x1 = LCA(x,y),y1 = st[x1][0];
            printf("%lld\n",lastans = query(root[x],root[y],root[x1],root[y1],1,nn,K));
        }
        else {
            int x = read()^lastans,y = read()^lastans;
            addedge(x,y); addedge(y,x);
            int fax = getf(x),fay = getf(y);
            if (sum[fax] > sum[fay]) swap(x,y),swap(fax,fay);
            dfs(x,y,fay);
        }
    }
    return 0;
}

/* Examples: */
/*

*/

/*

*/