P8460 「REOI-p1」按摩 题解

题目链接

题意

给出一个 n\times n 的网格，初始时有 m 个黑色点，其它的为白色点。

给出 k 次操作，每次操作使一个点黑白反转。求每次操作结束后是否存在一个以黑点作为顶点的所有边均平行于网格的多边形。

思路

这道题每次询问的内容是一个经典问题，具体的，对于每一个点，相当于它与它处在的行、列上的每一个其它点连一条边，这个我们可以用并查集维护，对于一次合并，如果两个点属于同一个集合，则会形成一个环。同时我们发现一个点存在的时间就是从白点变成黑点开始，直到又变回白点，这个我们可以用线段树分治维护。

在实现上，我们使用经典的线段树分治 + 可撤销并查集，对于每一行、列，建一个超级源点，减少合并次数，一个点的合并只用将它所处的行和列合并即可。

code

#include<bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
const int base=100000;
int t(1),n,m,k;
unordered_map<int,int>las;
unordered_map<int,bool>flag;
vector<int>dot;
struct edg{
    int u,v;
};
struct node{
    int l,r;
    vector<edg>e;
}tr[N<<2];
struct V_DSU{//可撤销并查集板子 
    int fa[N<<1],siz[N<<1],sta[N<<1],top;
    int gf(int x){return fa[x]==x?x:gf(fa[x]);} 
    void merge(int x,int y){
        int fx=gf(x),fy=gf(y);
        if(fx==fy)return;
        if(siz[fx]>siz[fy])swap(fx,fy);
        sta[++top]=fx;
        fa[fx]=fy;
        siz[fy]+=siz[fx];
    }
    void del(int res=0){
        while(top>res){
            siz[fa[sta[top]]]-=siz[sta[top]];
            fa[sta[top]]=sta[top];
            --top;
        }
    }
    bool together(int x,int y){return gf(x)==gf(y);}
}dsu;
void build(int x,int l,int r){
    tr[x].l=l,tr[x].r=r;
    if(l==r)return void();
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
void modi(int x,int l,int r,int u,int v){
    if(tr[x].l>r||tr[x].r<l)return void();
    if(tr[x].l>=l&&tr[x].r<=r){
        return tr[x].e.emplace_back((edg){u,v}),void();
    }
    modi(x<<1,l,r,u,v);
    modi(x<<1|1,l,r,u,v);
}
void dfs(int x){
    int rec=dsu.top,el=tr[x].e.size();
//  cout<<"     "<<x<<"("<<tr[x].l<<" "<<tr[x].r<<")"<<" "<<el<<"\n";
    for(int i=0;i<el;++i){
//      cout<<tr[x].e[i].u<<" "<<tr[x].e[i].v+n<<"\n";
        if(dsu.together(tr[x].e[i].u,tr[x].e[i].v+n)){
        //如果当前这些边已经形成环，则往下就算不再加边也存在环，直接全部输出 
            for(int j=tr[x].l;j<=tr[x].r;++j){
                cout<<"Yes\n";
            }
//          cout<<"back "<<x<<'\n';
            return dsu.del(rec),void();
        }
        dsu.merge(tr[x].e[i].u,tr[x].e[i].v+n);//我将列编号加了n,便于区分 
    }
    if(tr[x].l==tr[x].r){
        cout<<"No\n";
//      cout<<"back :"<<x<<"\n";
        return dsu.del(rec),void();//叶节点记得也要弹边 
    }
    dfs(x<<1);
    dfs(x<<1|1);
//  cout<<"back "<<x<<'\n';
    return dsu.del(rec),void();
}
signed main(){
    //cin>>t;
    while(t--){
        scanf("%lld%lld",&n,&m);
        for(int i=1,x,y;i<=m;++i){
            scanf("%lld%lld",&x,&y);
            if(flag.find(x*base+y)!=flag.end())continue; //抽象数据，初始包含重复点，需要特判 
            las[x*base+y]=1;
            flag[x*base+y]=true;
            dot.emplace_back(x*base+y);
        }
        for(int i=1;i<=n<<1;++i)dsu.fa[i]=i,dsu.siz[i]=1;
        scanf("%lld",&k);
        build(1,1,k);//时间轴是1~k 
        for(int i=1,x,y;i<=k;++i){
            scanf("%lld%lld",&x,&y);
            int id=x*base+y;
            if(flag.find(id)==flag.end()){
                flag[id]=true;
                las[id]=i;
                dot.emplace_back(id);
            }
            else{
                if(flag[id]){//flag为true说明当前是黑点 
                    modi(1,las[id],i-1,x,y);
                    flag[id]=false;
                }
                else{//否则为白点 
                    flag[id]=true;
                    las[id]=i;
                }
            }
        }
        for(auto x:dot){
        //没有配对的点相当于它从开始到结束一直存在 
            if(flag[x]){
                modi(1,las[x],k,x/base,x%base);
            }
        }
        dfs(1);
    }
    return 0;
}