主席树上树
写起来有点麻烦
这题两个操作
一个是查找路径上的第k大
一个是连边
首先处理树上路径第k大
如果要找(u->v)的第k大
那么一棵主席树u表示的是点u到根的每个权值出现了几次
所以求树上路径第k大就可以直接用(T_u + T_v - T_{lca(u,v)} - T_{fa(lca(u,v))})
这个非常简单
但是麻烦的是连边
要求强制在线
所以我们可以启发式合并主席树
每次连边都让size小的作为size大的的子树
然后重构size小的点的子树的倍增数组就好辣
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 1000005 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ;}
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
bool vis[M] ;
int n , m , T , tot , hea[M] , num ;
int f[M] , val[M] , s[M] , w[M] , dep[M] ;
int rt[M] , lg[M] , dis[M] , st[M][18] , size[M] ;
map < int , int > p ;
struct E {
int Nxt , to ;
} edge[M << 1] ;
struct Node { int l , r , sum ; } t[M << 5] ;
int Find(int x) {
if(f[x] != x) f[x] = Find(f[x]) ;
return f[x] ;
}
inline void add_edge(int from , int to) {
edge[++num].Nxt = hea[from] ;
edge[num].to = to ;
hea[from] = num ;
}
void Insert(int x , int l , int r , int &now) {
t[++tot] = t[now] ; now = tot ; t[now].sum ++ ;
if(l == r) return ;
int mid = (l + r) >> 1 ;
if(mid >= x) Insert(x , l , mid , t[now].l) ;
else Insert(x , mid + 1 , r , t[now].r) ;
}
int query(int k , int l , int r , int pre1 , int pre2 , int pre3 , int now) {
if(l == r) return l ;
int lsz = t[t[now].l].sum + t[t[pre3].l].sum - t[t[pre1].l].sum - t[t[pre2].l].sum ;
int mid = (l + r) >> 1 ;
if(k <= lsz) return query(k , l , mid , t[pre1].l , t[pre2].l , t[pre3].l , t[now].l) ;
else return query(k - lsz , mid + 1 , r , t[pre1].r , t[pre2].r , t[pre3].r , t[now].r) ;
}
void Dfs(int u , int father , bool ret) {
vis[u] = true ;
st[u][0] = father ; dep[u] = dep[father] + 1 ;
for(int i = 1 ; i <= 16 ; i ++)
st[u][i] = st[st[u][i - 1]][i - 1] ;
rt[u] = rt[father] ;
Insert(w[u] , 1 , n , rt[u]) ;
for(int i = hea[u] ; i ; i = edge[i].Nxt) {
int v = edge[i].to ;
if(v == father) continue ;
Dfs(v , u , ret) ;
if(!ret) continue ;
int x = Find(u) , y = Find(v) ;
if(x != y) f[y] = x , size[x] += size[y] ;
}
}
inline int LCA(int u , int v) {
if(dep[u] < dep[v]) swap(u , v) ;
for(int i = 16 ; i >= 0 ; i --)
if(dep[st[u][i]] >= dep[v])
u = st[u][i] ;
if(u == v) return u ;
for(int i = 16 ; i >= 0 ; i --)
if(st[u][i] != st[v][i])
u = st[u][i] , v = st[v][i] ;
return st[u][0] ;
}
int main() {
read() ;
n = read() ; m = read() ; T = read() ;
for(int i = 2 ; i <= n ; i ++) lg[i] = lg[i >> 1] + 1 ;
int tmp = 0 ;
for(int i = 1 ; i <= n ; i ++) {
w[i] = read() ; s[i] = w[i] ;
f[i] = i ; size[i] = 1 ;
}
sort(s + 1 , s + n + 1) ;
for(int i = 1 ; i <= n ; i ++) {
if(i == 1 || s[i] != s[i - 1]) ++ tmp ;
p[s[i]] = tmp ; val[tmp] = s[i] ;
}
for(int i = 1 ; i <= n ; i ++) w[i] = p[w[i]] ;
for(int i = 1 , u , v ; i <= m ; i ++) {
u = read() , v = read() ;
add_edge(u , v) ; add_edge(v , u) ;
}
for(int i = 1 ; i <= n ; i ++)
if(!vis[i])
Dfs(i , 0 , 1) ;
char opt[5] ;
int LastAns = 0 , x , y , k , lca , u , v ;
while(T --) {
scanf("%s",opt) ;
if(opt[0] == 'Q') {
x = read() , y = read() ; k = read() ;
x ^= LastAns ; y ^= LastAns ; k ^= LastAns ;
lca = LCA(x , y) ;
LastAns = val[query(k , 1 , n , rt[lca] , rt[st[lca][0]] , rt[x] , rt[y])] ;
printf("%d
",LastAns) ;
}
else {
x = read() , y = read() ;
x ^= LastAns , y ^= LastAns ;
u = Find(x) , v = Find(y) ;
if(size[u] < size[v]) swap(u , v) , swap(x , y) ;
f[v] = u ; size[u] += size[v] ;
Dfs(y , x , 0) ;
add_edge(x , y) ; add_edge(y , x) ;
}
}
return 0 ;
}