P15352 [COCI 2025/2026 #4] 魔术 / Magija

思路

倍增并查集，以下描述忽略反阿克曼函数 $\alpha(n)$。
首先考虑直接 $O(nq)$ 的维护，显然简单，用并查集维护哪些点可以相互到达，合并时压缩路径并统计答案，数据比较水所以甚至有 $73$ 分。

然后这个东西的时间复杂度瓶颈显然在修改操作，我们发现有些点会被重复合并，但是由于合并方式比较奇怪，我们不能很容易地记录那些点可以跳过不合并。
这时我们考虑一个很妙的数据结构：倍增并查集。
众所周知，倍增的时间复杂度是 $O(\log n)$，并查集的时间复杂度是 $O(n)$，那么将这两者结合的这个数据结构就是 $O(n\log n)$。
咋做呢？我们考虑在并查集根节点数组中添加一维 $k$ 代表合并的深度，即区间长度为 $2^k$。

  • 改写 find 操作：find 找本层的根节点值。
  • 改写 join 操作：join 只合并本层的值。

但是这样显然不对，我们需要增加一些操作：

  • merge：拆分每一个操作区间，也就是倍增部分；
  • update：维护答案，本题是单点查询所以只记录最低层（主要是出题人给了一个极小的空间限制）。

这两个操作怎么写呢？
首先讲解 merge：
我们每次将整个区间拆解成两个大小相等的子区间，分治地操作，层数减一，若不在最底层，则合并，若在最底层，则用 update 修改答案。
同时若要合并的两个值已经合并过了，则它们的子区间也一定合并过了，这也是本算法的优化之处。
再讲解 update：
首先默认是最底层，然后与 join 类似，只是多了一步答案更新。

对于每次 $l,r,len$ 的修改，我们倍增地 merge 操作，对应地更新 $l,r$ 端点即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
#define fir first
#define sec second 
//#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=2e5+47;
const int logN=18;
int n,q,fa[N][logN],mx[N],mi[N];
int find(int k,int x){
	if(x==fa[x][k])return x;
	return fa[x][k]=find(k,fa[x][k]);
}
void join(int k,int x,int y){
	int fx=find(k,x);
	int fy=find(k,y);
	if(fx==fy)return;
	fa[fx][k]=fy;
}
void update(int x,int y){
	int fx=find(0,x);
	int fy=find(0,y);
	if(fx==fy)return;
	mi[fx]=mi[fy]=min(mi[fx],mi[fy]);
	mx[fx]=mx[fy]=max(mx[fx],mx[fy]);
	fa[fx][0]=fy;
}
void merge(int l,int r,int k){
	if(k<0||find(k,l)==find(k,r))return;
	if(k>0)join(k,l,r);
	else update(l,r);
	merge(l,r,k-1);
	merge(l+(1<<(k-1)),r+(1<<(k-1)),k-1);
}
signed main(){
//	freopen("magija.in","r",stdin);
//	freopen("magija.out","w",stdout);
	read(n,q);
	rep(i,1,n){
		rep(j,0,17)fa[i][j]=i;
		mi[i]=mx[i]=i;
	}
	while(q--){
		int op;
		read(op);
		if(op==1){
			int x;read(x);
			int fx=find(0,x);
			print(mi[fx]);putchar(' ');
			print(mx[fx]);putchar('\n');
		}
		if(op==2){
			int l,r,len;
			read(l,r,len);
			per(i,17,0){
				if(len>=(1<<i)){
					merge(l,r,i);
					l+=(1<<i);
					r+=(1<<i);
					len-=(1<<i);
				}
			}
		}
	}
}
/*
5 3
2 3 4 1
1 5
1 3
*/