题目链接：P5064 [Ynoi2014] 等这场战争结束之后
题目大意：给你一个图，每个点有点权，最开始没有边。有一些操作：
- 添加一条 (x) 与 (y) 之间的双向边。
- 回到第 (x) 次操作后的状态（注意这里的 (x) 可以是 (0)，即回到初始状态）。
- 查询 (x) 所在联通块能到的点中点权第 (y) 小的值，如果不存在，那么输出
−1。
空间限制 19.53MB。
题解：离散化是不需要说的，不过离散化的时候不要合并相同的数就可以了。
显然发现二分查询 kth 不是很能做，所以直接考虑值域分块的做法，假设块长为 (B)。
我们发现我们能够把操作树建出来，于是最烦人的二操作我们只需要支持撤销就做完了。
因为值域分块求 kth 时需要知道整块内的数的个数和单点，所以分开来考虑。
然后我们先考虑单点怎么做：我们显然可以维护并查集，然后看一下这一个值所对应的位置是不是在当前的并查集内，单次查询是 (O(log n)) 的，所以一次是 (O(Blog n))。
接下来考虑整块，非常简洁的一个想法是对每一个点直接维护长度为 (frac{n}{B}) 的数组就可以了，然后合并的时候暴力合并。
然而我们发现这样空间复杂度是 (O(frac{n^2}{B})) 空间复杂度无法承受。
然后我们发现如果我们改成用链表启发式合并就变成 (O(nlog n)) 了，这非常优秀。
于是这里的合并的时间复杂度就是 (O(B)) 的。
于是我们取 (B=sqrt{frac{n}{log n}})，最后的时间复杂度就是 (O(msqrt{nlog n}))，空间复杂度就是 (O(nlog n))。
代码：
#include <cstdio>
#include <cassert>
#include <iostream>
#include <algorithm>
const int Maxn=100000;
const int Maxb=350;
const int Maxv=(Maxn-1)/Maxb+1;
const int Mask=(1<<15)-1;
const int Maxk=15;
int n,m;
int a[Maxn+5],rnk[Maxn+5];
namespace Input{
struct Node{
int a,id;
friend bool operator <(Node a,Node b){
return a.a<b.a;
}
}d[Maxn+5];
void init(){
for(int i=1;i<=n;i++){
scanf("%d",&d[i].a);
d[i].id=i;
}
std::sort(d+1,d+1+n);
for(int i=1;i<=n;i++){
a[d[i].id]=i;
}
for(int i=1;i<=n;i++){
rnk[a[i]]=i;
}
}
int query(int x){
return d[x].a;
}
}
namespace DSU{
int find_belong(int x){
return (x-1)/Maxb+1;
}
int find_bel_l(int x){
return (x-1)*Maxb+1;
}
int find_bel_r(int x){
return std::min(x*Maxb,n);
}
int fa[Maxn+5],sz[Maxn+5];
struct List{
int nxt;
int val;
}buc[Maxn*20+5];
int id_tot;
int head[Maxn+5];
void merge_lis(int id_x,int id_y){
if(head[id_y]==0){
return;
}
int lst_x=-1;
int pos_x=head[id_x],pos_y=head[id_y];
int v_x=buc[pos_x].val&Mask,v_y=buc[pos_y].val&Mask;
if(v_y<v_x){
id_tot++;
buc[id_tot].nxt=head[id_x];
buc[id_tot].val=buc[pos_y].val;
head[id_x]=id_tot;
pos_y=buc[pos_y].nxt;
lst_x=head[id_x];
}
else if(v_y==v_x){
buc[pos_x].val=(((buc[pos_x].val>>Maxk)+(buc[pos_y].val>>Maxk))<<Maxk)|v_x;
lst_x=pos_x;
pos_x=buc[pos_x].nxt;
pos_y=buc[pos_y].nxt;
}
else{
lst_x=pos_x;
pos_x=buc[pos_x].nxt;
}
while(pos_x&&pos_y){
v_x=buc[pos_x].val&Mask,v_y=buc[pos_y].val&Mask;
if(v_x==v_y){
buc[pos_x].val=(((buc[pos_x].val>>Maxk)+(buc[pos_y].val>>Maxk))<<Maxk)|v_x;
lst_x=pos_x;
pos_x=buc[pos_x].nxt;
pos_y=buc[pos_y].nxt;
}
else if(v_y<v_x){
id_tot++;
buc[id_tot].val=buc[pos_y].val;
buc[lst_x].nxt=id_tot;
buc[id_tot].nxt=pos_x;
lst_x=id_tot;
pos_y=buc[pos_y].nxt;
}
else{
lst_x=pos_x;
pos_x=buc[pos_x].nxt;
}
}
while(pos_y){
id_tot++;
buc[id_tot].val=buc[pos_y].val;
buc[lst_x].nxt=id_tot;
lst_x=id_tot;
pos_y=buc[pos_y].nxt;
}
}
void del_lis(int id_x,int id_y){
int pos_x=head[id_x],pos_y=head[id_y];
while(pos_x&&pos_y){
int v_x=buc[pos_x].val&Mask,v_y=buc[pos_y].val&Mask;
if(v_x==v_y){
buc[pos_x].val=(((buc[pos_x].val>>Maxk)-(buc[pos_y].val>>Maxk))<<Maxk)|v_x;
pos_x=buc[pos_x].nxt;
pos_y=buc[pos_y].nxt;
}
else if(v_y>v_x){
pos_x=buc[pos_x].nxt;
}
else{
assert(0);
}
}
}
int find(int x){
if(x==fa[x]){
return x;
}
return find(fa[x]);
}
std::pair<int,int> merge(int x,int y){
int fa_x=find(x),fa_y=find(y);
if(fa_x==fa_y){
return std::make_pair(-1,-1);
}
if(sz[fa_x]<sz[fa_y]){
std::swap(fa_x,fa_y);
std::swap(x,y);
}
fa[fa_y]=fa_x;
sz[fa_x]+=sz[fa_y];
merge_lis(fa_x,fa_y);
return std::make_pair(fa_x,fa_y);
}
void del(int x,int y){
sz[x]-=sz[y];
del_lis(x,y);
fa[y]=y;
}
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
sz[i]=1;
head[i]=++id_tot;
buc[head[i]].val=(1<<Maxk)|find_belong(a[i]);
}
}
int find_kth(int x,int k){
x=find(x);
int pos_x=head[x];
while(pos_x&&k>(buc[pos_x].val>>Maxk)){
k-=(buc[pos_x].val>>Maxk);
pos_x=buc[pos_x].nxt;
}
if(pos_x==0&&k>0){
return -1;
}
int bel=(buc[pos_x].val&Mask);
for(int i=find_bel_l(bel);i<=find_bel_r(bel);i++){
if(find(rnk[i])==x){
k--;
if(k==0){
return i;
}
}
}
return -1;
}
}
int ans[Maxn+5];
int q_u[Maxn+5],q_v[Maxn+5];
int head[Maxn+5],arrive[Maxn+5],nxt[Maxn+5],tot;
void add_edge(int from,int to){
arrive[++tot]=to;
nxt[tot]=head[from];
head[from]=tot;
}
void work_dfs(int u){
std::pair<int,int> tmp;
if(q_u[u]!=0){
if(q_v[u]<0){
ans[u]=DSU::find_kth(q_u[u],-q_v[u]);
}
else{
tmp=DSU::merge(q_u[u],q_v[u]);
}
}
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
work_dfs(v);
}
if(q_u[u]!=0){
if(q_v[u]>0){
if(tmp.first!=-1){
DSU::del(tmp.first,tmp.second);
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
Input::init();
DSU::init();
int lst=0;
for(int i=1;i<=m;i++){
int op;
scanf("%d",&op);
if(op==1){
scanf("%d%d",&q_u[i],&q_v[i]);
add_edge(lst,i);
}
else if(op==2){
int x;
scanf("%d",&x);
add_edge(x,i);
}
else{
scanf("%d%d",&q_u[i],&q_v[i]);
q_v[i]=-q_v[i];
add_edge(lst,i);
}
lst=i;
}
work_dfs(0);
for(int i=1;i<=m;i++){
if(q_v[i]<0){
if(ans[i]==-1){
printf("%d
",ans[i]);
}
else{
printf("%d
",Input::query(ans[i]));
}
}
}
return 0;
}
