CF1578B 题解

· · 题解

CF 官方题解做法。

不难发现一个连通块内部的连边情况不重要，我们可以将其视为一个多边形，即每个点连向下一个同连通块内的点。

断环成链，形成如下结构：

由于任意两个连通块不会相交，我们令 h_i 表示点 i 上方的边的数量。如图中 h_2=0,h_3=1,h_5=1。显然 \forall i\in [1,n),|h_i-h_{i+1}|\le 1。这是一个很好的性质。

来看连边操作。设连接 x,y，x<y 且 x,y 不在同一连通块内。分两种情况：

重复上述过程，直至 x 与 y 在同一连通块内。由于总合并次数为 O(n)，所以我们只需实现一个并查集，与一个能快速找到 p 的数据结构，并支持合并的数据结构即可。

注意到相邻点的 h 之差不超过 1，于是可以用线段树维护区间最小值，查询时线段树二分。

合并又分两种情况。用 l_i 表示 i 所在连通块的最左边的点，r_i 同理。若 r_x<l_y，则两连通块没有包含关系，要加一条边，h 区间 +1；否则有包含关系，要删一条边，加两条边，区间 -1。可以用线段树维护。

于是此题得解。复杂度 O(n\log n)。常数很小，实测 498\text{ms}。

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m;
struct dsu {
    int fa[N],l[N],r[N];
    void init() {for(int i=1;i<=n;i++) fa[i]=l[i]=r[i]=i;}
    int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);}
    void merge(int x,int y) {
        x=get(x); y=get(y);
        if(x==y) return ;
        fa[x]=y; l[y]=min(l[x],l[y]); r[y]=max(r[x],r[y]);
    }
} s;
struct sgt {
    int mn[4*N],add[4*N];
    void pushval(int p,int v) {mn[p]+=v; add[p]+=v;}
    void pushdown(int p) {
        if(!add[p]) return ;
        pushval(p<<1,add[p]); pushval(p<<1|1,add[p]);
        add[p]=0;
    }
    void modify(int L,int R,int v,int p=1,int l=1,int r=n) {
        if(L>R) return ;
        if(L<=l&&r<=R) {pushval(p,v); return ;}
        int mid=l+r>>1; pushdown(p);
        if(L<=mid) modify(L,R,v,p<<1,l,mid);
        if(R>mid) modify(L,R,v,p<<1|1,mid+1,r);
        mn[p]=min(mn[p<<1],mn[p<<1|1]);
    }
    int query(int x,int p=1,int l=1,int r=n) {
        if(l==r) return mn[p];
        int mid=l+r>>1; pushdown(p);
        if(x<=mid) return query(x,p<<1,l,mid);
        return query(x,p<<1|1,mid+1,r);
    }
    int binaryl(int x,int v,int p=1,int l=1,int r=n) {
        if(r<=x) {
            if(mn[p]>=v) return 0;
            if(l==r) return l;
            int mid=l+r>>1; pushdown(p);
            if(mn[p<<1|1]<v) return binaryl(x,v,p<<1|1,mid+1,r);
            return binaryl(x,v,p<<1,l,mid);
        }
        int mid=l+r>>1,res=0; pushdown(p);
        if(mid+1<=x) res=binaryl(x,v,p<<1|1,mid+1,r);
        if(!res) res=binaryl(x,v,p<<1,l,mid);
        return res;
    }
    int binaryr(int x,int v,int p=1,int l=1,int r=n) {
        if(x<=l) {
            if(mn[p]>=v) return n+1;
            if(l==r) return l;
            int mid=l+r>>1; pushdown(p);
            if(mn[p<<1]<v) return binaryr(x,v,p<<1,l,mid);
            return binaryr(x,v,p<<1|1,mid+1,r);
        }
        int mid=l+r>>1,res=n+1; pushdown(p);
        if(x<=mid) res=binaryr(x,v,p<<1,l,mid);
        if(res==n+1) res=binaryr(x,v,p<<1|1,mid+1,r);
        return res;
    }
} t;
void merge(int x,int y) {
    x=s.get(x); y=s.get(y);
    if(s.r[x]<s.l[y]) t.modify(s.r[x]+1,s.l[y]-1,1);
    else t.modify(max(s.l[x],s.l[y]),min(s.r[x],s.r[y]),-1);
    s.merge(x,y);
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    s.init();
    while(m--) {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1) {
            if(x>y) swap(x,y);
            int vx=t.query(x),vy=t.query(y);
            while(s.get(x)!=s.get(y)) {
                if(vx>vy) {merge(x,t.binaryr(x,vx)); vx--;}
                else if(vx<vy) {merge(t.binaryl(y,vy),y); vy--;}
                else {
                    int p=t.binaryr(x,vx);
                    if(p<y) {merge(x,p); vx--;}
                    else merge(x,y);
                }
            }
        }
        else cout<<(s.get(x)==s.get(y));
    }
    return 0;
}