P15352

Gaochenxi103_QAQ · 2026-04-23 12:06:36 · 题解

做法

一个经典的 trick。

首先对于 O(nq) 做法是容易的。（忽略并查集常数）

观察主要问题在于操作 2，假如 l+i 和 r+i 已经属于同一个并查集。无意义的操作就会增加时间复杂度，考虑优化这个处理。

有没有什么高效的结构可以处理这个。于是就有了并查集加 ST 表的处理。新增一个数组 f_{k,i}，表示 [i,i+2^k-1] 这个区间的状态。如果 f_{k,i}=f_{k,j}，说明之前就已经处理过 [i,i+2^k-1] 和 [j,j+2^k-1] 这两个区间的一一对应。

然后如果 A,B 两个区间处理过，B,C 也处理过。即使 A,C 没有互相直接处理过，但也不需要再额外处理了。所以 f_{k,i} 也可以认为是一个并查集数组，来表示长度为 2^k 的区间之间的已操作关系。

实现一个函数merge(x,y,k)，表示处理 [x,x+2^k-1] 和 [y,y+2^k-1] 这两区间的一一对应操作。

• 如果 f_{x,k}=f_{y,k}，直接结束函数。说明之后的操作已处理。
• 接下来如果 k=0，直接做 x,y 的普通合并。与暴力代码一致。
• 否则考虑下放合并指令merge(x,y,k-1)和merge(x+(1<<(k-1)),y+(1<<(k-1)),k-1)。
• 最后 f_{x,k} 和 f_{y,k} 合并，表示两者之间已经互相操作过了。

每次查询的 [l,r]，用类似 ST 表查询的方式冗余合并即可。示例。

int l,r,len;cin>>l>>r>>len;
int k=log2(len);
merge(l,r,k);
merge(l+len-1-(1<<k)+1,r+len-1-(1<<k)+1,k);

对于查询，和暴力代码一致。

注意到每层 f_{x,k} 最多 O(n) 次合并，然后一共是 \log n 层。所以时间复杂度为 O(n\log n)。

总结一下：用分治的思想，巧妙的节省了大量无意义合并。

代码

::::success[Accepted code]

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=2e5+10;
int n,fa[20][N],mx[N],mi[N],T;
void init()
{
    for(int i=0;i<=19;i++)
    {
        for(int j=1;j<=n;j++)
        {
            fa[i][j]=j;
        }
    }
    for(int i=1;i<=n;i++)mx[i]=mi[i]=i;
}
int findmi(int x)
{
    if(mi[x]==x)return x;
    return mi[x]=findmi(mi[x]);
}
int findmx(int x)
{
    if(mx[x]==x)return x;
    return mx[x]=findmx(mx[x]);
}
int find(int x,int k)
{
    if(fa[k][x]==x)return x;
    return fa[k][x]=find(fa[k][x],k);
}
void merge(int x,int y,int k)
{
    int fx=find(x,k),fy=find(y,k);
    if(fx==fy)return;
    if(k==0)
    {
        fx=findmi(x),fy=findmi(y);
        if(fx>fy)mi[fx]=fy;
        else mi[fy]=fx;
        fx=findmx(x),fy=findmx(y);
        if(fx<fy)mx[fx]=fy;
        else mx[fy]=fx;
        return ;
    }
    merge(x,y,k-1);
    merge(x+(1<<(k-1)),y+(1<<(k-1)),k-1);
    fa[k][fy]=fx;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>T;
    init();
    while(T--)
    {
        int op;cin>>op;
        if(op==1)
        {
            int x;cin>>x;
            cout<<findmi(x)<<" "<<findmx(x)<<"\n";
        }
        else
        {
            int l,r,len;cin>>l>>r>>len;
            int k=log2(len);
            merge(l,r,k);
            merge(l+len-1-(1<<k)+1,r+len-1-(1<<k)+1,k);
        }
    }
    return 0;
}

::::