题目id:15765
题意
给定 n \leq 100000 个节点，每个节点有权值，有 m \leq 100000 个操作
共三种操作
\quad opt_1: 连边: 连接节点 u 和 v
\quad opt_2: 回退: 返回至操作 x 完成后的状态
\quad opt_3: 查询: 输出节点 u 能到达的第 k 大的节点
思路
因为看到有回退的操作，所以立马想到了主席树，
但是其实这题没有说强制在线，可以 离线 建操作树+并查集&分块维护答案
1. 建一颗操作树，以每一个操作作为树上的节点。
回退操作则将当前节点挂在返回的目标节点下，非返回操作将当前节点挂在前一个操作的节点下。
遍历操作树统计答案，每次回溯时完成删边，遍历时完成加边和查询
2. 用并查集维护能否到达
由于会有删边操作，所以并查集不可以压缩路径。 合并时将并查集节点个数小的连到大的上面
3. 将所有节点按照节点点权从小到大排序并分块。
由于空间很大可以直接开数组 f[i][j] 表示 i 号节点在块 j 内有多少个点可以到达。
统计答案时，直接暴力枚举答案在块 i 内，再在块 i 内枚举答案 j
code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100110;
struct node{
int fr,to,ne;
}ed[N*2];
struct numbe{
int num,id;
}val[N];
int he[N],n_e=0;
int fom[N],len=0,n,m;
int opt[N][5];
int f[N][410],L[N],R[N],bel[N],length,fat[N],siz[N];
void add(int x,int y){
ed[++n_e].fr=x;ed[n_e].to=y;ed[n_e].ne=he[x];he[x]=n_e;
}
void update(int x,int y){
for(int i=1;i<=n/length;i++)f[y][i]+=f[x][i];
}
int find(int x){
if(fat[x]==x)return x;
else return find(fat[x]);
}
void del(int x,int y){
for(int i=1;i<=n/length;i++)f[y][i]-=f[x][i];
}
int query(int x,int k){
int fx=find(x);
if(k>siz[fx])return -1;
for(int i=1;i<=n/length;i++){
if(k<=f[fx][i]){
for(int j=L[i];j<=R[i];j++)
if(find(val[j].id)==fx){
k--;
if(k==0)return val[j].num;
}
}
k-=f[fx][i];
}
}
void dfs(int x,int fa){
int flag=0;
if(opt[x][0]==1){
opt[x][1]=find(opt[x][1]);opt[x][2]=find(opt[x][2]);
if(opt[x][1]!=opt[x][2]){
if(siz[opt[x][1]]>siz[opt[x][2]])swap(opt[x][1],opt[x][2]);
siz[opt[x][2]]+=siz[opt[x][1]];fat[opt[x][1]]=opt[x][2];flag=1;
update(opt[x][1],opt[x][2]);
}
}
if(opt[x][0]==3)opt[x][3]=query(opt[x][1],opt[x][2]);
for(int i=he[x];i!=-1;i=ed[i].ne){
int y=ed[i].to;
if(y==fa)continue;
dfs(y,x);
}
if(flag){
del(opt[x][1],opt[x][2]);
siz[opt[x][2]]-=siz[opt[x][1]];
fat[opt[x][1]]=opt[x][1];
}
}
bool cmp(numbe x,numbe y){return x.num<y.num;}
int main(){
memset(he,-1,sizeof(he));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&val[i].num);
val[i].id=i;
}
sort(val+1,val+n+1,cmp);
length=sqrt(n);
for(int i=1;i<=n/length;i++){
L[i]=(i-1)*length+1,R[i]=i*length;
if(i==n/length)R[i]=n;
for(int j=L[i];j<=R[i];j++)bel[j]=i;
}
for(int i=1;i<=n;i++){
fat[i]=i;siz[i]=1;
f[val[i].id][bel[i]]++;
}
for(int i=1;i<=m;i++){
int op;
scanf("%d",&opt[i][0]);
if(opt[i][0]==2){
int x;
scanf("%d",&opt[i][1]);
add(opt[i][1],i);
}
else{
scanf("%d%d",&opt[i][1],&opt[i][2]);
add(i-1,i);
}
}
dfs(0,0);
for(int i=1;i<=m;i++)
if(opt[i][0]==3)printf("%d\n",opt[i][3]);
return 0;
}
原题
luogu P5064
由于洛谷上题目有空间限制，所以删掉非必要数组。
对于 f[i][j] 将块长调为 45 左右 并用 short 存（ n / 块长 不会超 short ）