森林
题意:有两种操作:
1. 将某两个点连起来(连边后保证为森林或者一棵树)
2. 询问两点之间路径上第K小权值(强制在线且保证询问合法)
思路:树上主席树+启发式合并
- 先离散化一下还是有必要的
- 连边后分别在每一棵树上建立主席树,每一棵树上的每一个节点的主席树维护从所在的树根到当前节点路径上的权值
- 合并的过程用比较小的树合并大比较大的树上
- 求解询问的关键: s=sz[L[x]]+sz[L[y]]−sz[L[lca]]−sz[L[flca]],这样可以计算出 x到 y的路径上的权值个数,所以我们需要的是 x,y,lca(x,y),fa[lca(x,y)]这四个值
- 然后随便写个倍增求 lca的函数,好像就完事了?
- 嗯,差不多了,但是数组尽量开大点,毕竟每合并一次又需要更多的节点,并且你不知道要合并多少次。。。我开 64被RE了两个点,然后索性直接开了256倍A掉了。
题面描述
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 8e4+10;
const int mod = 1e9+7;
const double eps = 1e-7;
int N, M, t, maxp;
int a[maxn], b[maxn], fa[maxn], st[maxn][18], vis[maxn], at[maxn], dp[maxn];
int head[maxn], son[maxn], to[maxn*2], nxt[maxn*2], cnt;
int T[maxn<<8], L[maxn<<8], R[maxn<<8], sz[maxn<<8], tot;
inline void add_edge(int u, int v) {
++cnt, to[cnt]=v, nxt[cnt]=head[u], head[u]=cnt;
++cnt, to[cnt]=u, nxt[cnt]=head[v], head[v]=cnt;
}
void update(int d, int l, int r, int pre, int &now) {
now=++tot;
L[now]=L[pre], R[now]=R[pre], sz[now]=sz[pre]+1;
if(l==r) return;
int m=(l+r)/2;
if(d<=m) update(d,l,m,L[pre],L[now]);
else update(d,m+1,r,R[pre],R[now]);
}
int query(int k, int x, int y, int lca, int flca, int l, int r) {
if(l==r) return l;
int s=sz[L[x]]+sz[L[y]]-sz[L[lca]]-sz[L[flca]];
int m=(l+r)/2;
if(s>=k) return query(k,L[x],L[y],L[lca],L[flca],l,m);
else return query(k-s,R[x],R[y],R[lca],R[flca],m+1,r);
}
void dfs(int u, int f, int rt) {
son[rt]++, fa[u]=st[u][0]=f, vis[u]=1, at[u]=rt, dp[u]=dp[f]+1;
for(int i=1; i<18; ++i) st[u][i]=st[st[u][i-1]][i-1];
update(a[u],1,maxp,T[f],T[u]);
for(int i=head[u]; i; i=nxt[i]) if(to[i]!=f) dfs(to[i],u,rt);
}
inline int lca(int x, int y) {
if(dp[x]<dp[y]) swap(x,y);
int d=dp[x]-dp[y];
for(int i=17; i>=0; --i) if(d>=(1<<i)) d-=1<<i, x=st[x][i];
if(x==y) return x;
for(int i=17; i>=0; --i) if(st[x][i]!=st[y][i]) x=st[x][i], y=st[y][i];
return fa[x];
}
int main() {
//ios::sync_with_stdio(false); cin.tie(0);
int testcase=read();
N=read(), M=read(), t=read();
for(int i=1; i<=N; ++i) a[i]=b[i]=read(), at[i]=i;
sort(b+1,b+1+N); maxp=unique(b+1,b+1+N)-b-1;
for(int i=1; i<=N; ++i) a[i]=lower_bound(b+1,b+1+maxp,a[i])-b;
for(int i=1; i<=M; ++i) add_edge(read(),read());
for(int i=1; i<=N; ++i) if(!vis[i]) dfs(i,0,i);
int lastans=0;
while(t--) {
char op[2]; scanf("%s", op);
int x=read()^lastans, y=read()^lastans, LCA;
if(op[0]=='Q') LCA=lca(x,y), printf("%d\n", lastans=b[query(read()^lastans,T[x],T[y],T[LCA],T[fa[LCA]],1,maxp)]);
else {
add_edge(x,y);
if(son[at[x]]<son[at[y]]) swap(x,y);
dfs(y,x,at[x]);
}
}
}
再补充一个压了行的简短代码,QAQ
#include "bits/stdc++.h"
using namespace std;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 8e4+10;
int N, M, t, maxp, lastans;
int a[maxn], b[maxn], fa[maxn], st[maxn][18], vis[maxn], at[maxn], dp[maxn];
int head[maxn], son[maxn], to[maxn*2], nxt[maxn*2], cnt;
int T[maxn<<7], L[maxn<<7], R[maxn<<7], sz[maxn<<7], tot;
inline void add_edge(int u, int v) {
++cnt, to[cnt]=v, nxt[cnt]=head[u], head[u]=cnt;
++cnt, to[cnt]=u, nxt[cnt]=head[v], head[v]=cnt;
}
void update(int d, int l, int r, int pre, int &now) {
now=++tot;
L[now]=L[pre], R[now]=R[pre], sz[now]=sz[pre]+1;
if(l==r) return;
int m=(l+r)/2;
if(d<=m) update(d,l,m,L[pre],L[now]);
else update(d,m+1,r,R[pre],R[now]);
}
int query(int k, int x, int y, int lca, int flca, int l, int r) {
if(l==r) return l;
int s=sz[L[x]]+sz[L[y]]-sz[L[lca]]-sz[L[flca]];
int m=(l+r)/2;
if(s>=k) return query(k,L[x],L[y],L[lca],L[flca],l,m);
else return query(k-s,R[x],R[y],R[lca],R[flca],m+1,r);
}
void dfs(int u, int f, int rt) {
son[rt]++, fa[u]=st[u][0]=f, vis[u]=1, at[u]=rt, dp[u]=dp[f]+1;
for(int i=1; i<18; ++i) st[u][i]=st[st[u][i-1]][i-1];
update(a[u],1,maxp,T[f],T[u]);
for(int i=head[u]; i; i=nxt[i]) if(to[i]!=f) dfs(to[i],u,rt);
}
inline int lca(int x, int y) {
if(dp[x]<dp[y]) swap(x,y);
int d=dp[x]-dp[y];
for(int i=17; i>=0; --i) if(d>=(1<<i)) d-=1<<i, x=st[x][i];
if(x==y) return x;
for(int i=17; i>=0; --i) if(st[x][i]!=st[y][i]) x=st[x][i], y=st[y][i];
return fa[x];
}
int main() {
int testcase=read();
N=read(), M=read(), t=read();
for(int i=1; i<=N; ++i) a[i]=b[i]=read(), at[i]=i;
sort(b+1,b+1+N); maxp=unique(b+1,b+1+N)-b-1;
for(int i=1; i<=N; ++i) a[i]=lower_bound(b+1,b+1+maxp,a[i])-b;
for(int i=1; i<=M; ++i) add_edge(read(),read());
for(int i=1; i<=N; ++i) if(!vis[i]) dfs(i,0,i);
while(t--) {
char op[2]; scanf("%s", op);
int x=read()^lastans, y=read()^lastans, LCA;
if(op[0]=='Q') LCA=lca(x,y), printf("%d\n", lastans=b[query(read()^lastans,T[x],T[y],T[LCA],T[fa[LCA]],1,maxp)]);
else {
add_edge(x,y);
if(son[at[x]]<son[at[y]]) swap(x,y);
dfs(y,x,at[x]);
}
}
}