维护全局单值修改的数据结构

名字是自己取的。

问题：

初始序列 $a$ 中第 $i$ 个元素为 $i$。每次修改操作将所有等于 $x$ 的元素修改成 $y$。每次查询操作查询某个位置上的值。

解法：

并查集，动态开点。预处理时将每个结点（值）各自指向一个单独的新结点，新结点存储该点代表的值。用一个数组记录值代表的点。

- 修改：新开一个点，将旧值和新值代表的点指向这个点，并将旧值代表的点删除。
- 查询：直接路径压缩地查询即可。

记成代码既是：数组中，记从点到新结点为 $\text{PtN}(point\_to\_next)$，记值到结点为 $\text{VtP}(val\_to\_point)$，结点权值为 $\text{Val}$。

修改 `x y`：新建 $c$ 结点，将 $\text{PtN}[\text{PtN}'[\text{VtP}(x)]]$ 和 $\text{PtN}[\text{PtN}'[\text{VtP}(y)]]$ $\leftarrow c$（注意这里的 $\text{PtN}'$ 是递归找到的 $\text{PtN}$），将 $\text{PtN}[c] \leftarrow c$， 将 $\text{VtP}[x]\leftarrow0$，将 $\text{VtP}[y]\leftarrow c$，将 $\text{Val}[c]=y$。

查询 `x`：从 $\text{VtP[x]}$ 开始跳 $\text{PtN[x]}$ 直到找到 $\text{PtN}$ 等于自身的，输出其 $\text{Val[x]}$。

时间复杂度：$O(n\alpha(n))$。

改成区间查询，上分块可以做到 $O(n\sqrt n \cdot\alpha (n))$。

可能有更简单的做法？

```
#include<bits/stdc++.h>

using namespace std;

const int N=2000010;

int n,V,q,PtN[N],VtP[N],Val[N],c;

int get_PtN(int x)
{
	if(PtN[x]==x) return x;
	return PtN[x]=get_PtN(PtN[x]);
}

int main()
{
//	freopen("extra_bcj.in","r",stdin);
//	freopen("extra_bcj.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>V>>q;
	c=V;
	for(int v=1;v<=V;++v)
	{
		++c;
		PtN[v]=c;
		PtN[c]=c;
		VtP[v]=c;
		Val[c]=v;
	}
	while(q--)
	{
		int opt,x,y;
		cin>>opt>>x;
		if(opt==1)
		{
			cin>>y;
			if(x==y) continue;
			++c;
			if(get_PtN(VtP[x])==0) continue;
			PtN[get_PtN(VtP[x])]=c;
			if(VtP[y]!=0) PtN[get_PtN(VtP[y])]=c;
			PtN[c]=c;
			VtP[x]=0;
			VtP[y]=c;
			Val[c]=y;	
		}	
		else
		{
			cout<<Val[get_PtN(x)]<<'\n';
		}
	} 
    return 0;
}
```

经对拍已验证其正确性。