链接：https://ac.nowcoder.com/acm/contest/69510/G
来源：牛客网
你在一个星球上，外星人amiloac想让你管理一条河流，该河流有\(x\)段，每两段之间有一个挡板隔开，每一段都有各自的颜色\(a\)。你需要管理\(q\)天，每一天你需要做以下的一种操作。
\(1\ l\ r\)将第\(l\)至\(r\)段河流的所有未打开的挡板打开。
\(2\ x\)询问你第\(x\)段河流的颜色是什么。
对于任意相邻的两段，它们之间的隔板被打开后的瞬间，河流的颜色会混合变成颜色最深的河流的颜色，\(a\)越大，颜色越深。
注：隔板打开后，河流的段数不会变。请注意不同寻常的空间限制！
第一行为两个整数\(n,q(1\le n \le 5 \cdot 10^5),(1\le q\le 5 \cdot 10^5)\)，分别表示河流的段数和管理的天数。
第二行为\(n\)个整数\(a_i(1\le i\le n),(1\le a_i\le 10^9)\),表示每一段河流的颜色。
接下来\(q\)行每行第一个数\(op(1\le op\le 2)\)表示操作：
如果\(op=1\)，则给出两个数\(l,r(1\le l\le r\le n)\)，表示你需要将第\(l\)至\(r\)段河流的所有未打开的挡板打开；
如果\(op=2\)，则给出一个数\(x(1\le x\le n)\)，表示询问你第\(x\)段河流的颜色是什么。
对于每次操作\(2\)，输出一个整数\(ans\)，表示第\(x\)段河流的颜色。
解法：并查集。
每一次打开挡板，便将当前的河段与下一段河流合并，然后跳到下一段尚未与当前河段合并的河流继续合并。
本题卡空间把线段树卡掉了。
int n, m;
int a[N];
int fa[N];
int nx[N];
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]) ; }
void solve(){
int q;cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)fa[i]=i,nx[i]=i+1;
for(int i=1;i<=q;i++){
int op;cin>>op;
if(op==1){
int l,r;cin>>l>>r;
int g;
while(nx[get(l)]<=r){
int x=get(l),y=get(nx[x]);
fa[x]=y;
a[y]=max(a[x],a[y]);
//nx[l]表示下一个和l不在同一个连通块的点
//nx[get(l)]表示下一个和l的的根节点的点
//本质上根节之间跳来跳去
l=nx[x];
}
}
else {
int x;cin>>x;
cout << a[get(x)] << '\n' ;
}
}
}