分享一下阎帝的解法。

思路

首先不难以下几点： 1.发现操作池中一个操作操作两次相当于无效操作，没有意义。 2.每一次操作即让一个点可以最终到达的点多增加一个 3.操作的顺序不会实际影响结果 4.我们只需记录$x$点能够到达那些位置，记录下最大最小值即可。

既然如此，我们只需维护一个并查集，再额外开两个变量，表示一个点能够到达的位置最大最小值。

但是暴力维护肯定会TLE，考虑使用区间并查集优化一手，其核心思想就是通过倍增来快速对一个区间进行合并。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fa[21][N],n,ma[N],mi[N];
int find(int c,int x){return fa[c][x]==x?fa[c][x]:(fa[c][x]=find(c,fa[c][x]));}
void merge(int c,int x,int y)
{
	int tx=find(c,x),ty=find(c,y);
	if(tx!=ty)
	{
		fa[c][tx]=ty;
		ma[ty]=max(ma[ty],ma[tx]);
		mi[ty]=min(mi[ty],mi[tx]);
		if(c)
		{
			merge(c-1,x,y);
			merge(c-1,x+(1<<(c-1)),y+(1<<(c-1)));
		}
	}
}
int main()
{
	int n,q;scanf("%d%d",&n,&q);
	for(int i=0;i<20;i++)for(int j=1;j<=n;j++)fa[i][j]=j,ma[j]=mi[j]=j;
	while(q--)
	{
		int op,x,y,l;scanf("%d%d",&op,&x);
		if(op==1)
		{
			int tx=find(0,x);
			printf("%d %d\n",mi[tx],ma[tx]);
		}
		else
		{
			scanf("%d%d",&y,&l);
			int lg=log2(l);
			merge(lg,x,y);merge(lg,x+l-(1<<lg),y+l-(1<<lg));
		}
	}
}

出题人脑子有洞吧只给32MiB……

阎帝 nb

交换是不限次数的，问的还是 x 能到达的左右端。

相当于将两个区间同属，同属的区间共享左右端。

明显区间倍增并查集。

这题跟 P3295 [SCOI2016] 萌萌哒 很像，可以也看看这个题。

题意简单就不讲了

传送门

分析

我们考虑一个操作对于某个 $x$ 位置（这个操作范围包含这个位置）的影响，明显会和另外一个位置（令其为 $y$）互换。由于“一个操作可以被使用多次”，所以以后 $x$ 和 $y$ 的位置随时可以交换。当 $x$ 和另外一个位置 $z$ 互换时，$y$ 也可以和 $z$ 的位置互换。我们把它们看成一个整体，一个整体内的数是可以随意互换的，一个整体内的答案当然是相同的。这个是可以用并查集维护的。

直接维护时间复杂度为 $O(nq)$ （并查集复杂度忽略）。

那怎么优化呢？ 我们发现假如上一个操作为 $(4,8,3)$，又来一个操作为 $(2,6,5)$。这时候区间 $[4,6]$ 和 $[8,10]$ 在上一个操作时合并了，又来一个操作时，又尝试合并一次，时间复杂度就浪费在这里了。

具体做法是：建立 $\log n$ 层的并查集 $f_{i,j}$ 表示的是以 $j$ 开头长度为 $2^i$ 的块，用以标记这个块的合并情况。 这时我们来一个操作就把它按二进制拆开来合并，例如：$(2,8,5)$ 就拆成 $(2,8,4)$ 和 $(6,12,1)$ 来合并。如果发现合并过了，就直接跳过，否则就直接往下，往更小的块合并

非常非常具体的：建立一个函数 $merge(l,r,k)$ 表示合并区间 $[l,l+2^k-1]$ 和 $[r,r+2^k-1]$。如果发现 $f_{k,l}$ 和 $f_{k,r}$ 合并过了直接退出，否则合并 $f_{k,l}$ 和 $f_{k,r}$ 并递归 $merge(l,r,k-1)$ 和 $merge(l+2^{k-1},r+2^{k-1},k-1)$。

上图展示了合并过程。

答案就只要在最后一层统计就行了（否则会 MLE）。

时间复杂度

虽然一次修改时间复杂度可能达到 $O(n)$，但是并查集点的个数只有 $O(n\log n)$，又在发现合并后直接退出，总共时间复杂度只有 $O(n\log n)$。这题有点卡空间，我写了启发式合并并查集卡不过去（MLE），所以只有路径压缩，故时间复杂度为 $O(n\log^2 n)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,q;
int f[18][N];
struct node{
	int mi,mx;
}g[N];
int find(int c,int x){
	if(x==f[c][x]) return x;
	return f[c][x]=find(c,f[c][x]);
}
void unit(int c,int x,int y){ //正常合并并查集
	x=find(c,x),y=find(c,y);
	if(x^y){
		f[c][x]=y;
	}
}
void qix(int x,int y){ //统计答案
	x=find(0,x),y=find(0,y);
	if(x^y){
		g[y].mi=min(g[y].mi,g[x].mi);
		g[y].mx=max(g[y].mx,g[x].mx);
		f[0][x]=y;
	}
}
bool check(int c,int x,int y){
	x=find(c,x),y=find(c,y);
	return x^y;
}
void merge(int l,int r,int k){
	if(k<0||!check(k,l,r)) return ;
	if(k>0) unit(k,l,r);
	else qix(l,r);
	merge(l,r,k-1);
	merge(l+(1<<(k-1)),r+(1<<(k-1)),k-1);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>q;
	for(int s=0;s<=17;s++)
		for(int i=1;i<=n;i++)
			f[s][i]=i;
	for(int i=1;i<=n;i++)
		g[i]={i,i};
	for(int i=1;i<=q;i++){
		int op,x,l,r,len;
		cin>>op;
		if(op==1){
			cin>>x;
			x=find(0,x);
			cout<<g[x].mi<<" "<<g[x].mx<<"\n";
		}else{
			cin>>l>>r>>len;
			for(int j=17;j>=0;j--){
				if(len>>j&1)
					merge(l,r,j),l+=(1<<j),r+=(1<<j);
			}
		}
	}
	return 0;
}