题解归档 - cf813F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf813F
• 本地来源：problems/cf813F/idea.md
• 题目链接：https://codeforces.com/contest/813/problem/F
• 原始标题：CF813F Bipartite Checking

思路

CF813F Bipartite Checking

题意

$n$ 点无向图，初始无边。$q$ 次操作，每次 toggle 边 $(x,y)$：有则删、无则加。每次操作后判断当前图是否二分图，输出 YES/NO。

做法

离线 + 线段树分治 + 带撤销的并查集（奇偶性）。

1. 读入全部操作，对每条边记录 toggle 时刻；相邻 toggle 之间该边存在的时间段挂到线段树对应区间。
2. 最后仍存在的边挂到 [last_toggle, q-1]。
3. DFS 线段树：进入节点时合并该节点边集；unite(u,v,1) 表示 $u,v$ 必须异色（奇偶并查集）；冲突则该时刻及子区间标记 NO。
4. 离开节点 rollback 撤销并查集。

get(u) 返回 root*2+parity，unite 按扩展域并查集合并；dfs 向子节点传递当前是否已冲突。

复杂度

$O((n+q)\log q)$。

验证

• 样例通过
• WSL 本地对拍 500 组（Kali SSH 不可达，未走 stress.py）

代码

来源：problems/cf813F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:51:30
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
ll fa[maxn],sz[maxn],xr[maxn],n,q,i,j,k,x,y,cur,pd,zc;
vector<pair<ll,ll>>seg[maxn*4];
map<pair<ll,ll>,ll>mp;
struct stk{
    ll u,fa,sz,xr;
}ss[maxn*40];
ll top;
ll get(ll u){
    ll cur=0;
    while(fa[u]!=u){
        cur^=xr[u];
        u=fa[u];
    }
    return u*2+cur;
}
ll unite(ll u,ll v,ll w){
    ll ru=get(u),rv=get(v);
    u=ru/2;
    v=rv/2;
    ll pu=ru%2,pv=rv%2;
    if(u==v) return (pu^pv)==w;
    if(sz[u]>sz[v]) swap(u,v),swap(pu,pv);
    ss[++top]={v,fa[v],sz[v],xr[v]};
    fa[v]=u;
    sz[u]+=sz[v];
    xr[v]=pu^pv^w;
    return 1;
}
void rollback(ll lim){
    while(top>lim){
        ll v=ss[top].u;
        fa[v]=ss[top].fa;
        sz[v]=ss[top].sz;
        xr[v]=ss[top].xr;
        top--;
    }
}
void add(ll id,ll l,ll r,ll ql,ll qr,ll u,ll v){
    if(ql>r or qr<l) return;
    if(ql<=l and r<=qr){
        seg[id].push_back({u,v});
        return;
    }
    ll mid=(l+r)/2;
    add(id*2,l,mid,ql,qr,u,v);
    add(id*2+1,mid+1,r,ql,qr,u,v);
}
void dfs(ll id,ll l,ll r,ll pd){
    ll lim=top,cur=pd;
    for(autop:seg[id]) if(!cur and !unite(p.first,p.second,1)) cur=1;
    if(l==r) cout<<(cur?"NO":"YES")<<"\n";
    else{
        ll mid=(l+r)/2;
        dfs(id*2,l,mid,cur);
        dfs(id*2+1,mid+1,r,cur);
    }
    rollback(lim);
}
int main(){
    cin>>n>>q;
    for(i=0;i<q;i++){
        cin>>x>>y;
        if(x>y) swap(x,y);
        if(mp.count({x,y})){
            add(1,0,q-1,mp[{x,y}],i-1,x,y);
            mp.erase({x,y});
        }else mp[{x,y}]=i;
    }
    for(autop:mp) add(1,0,q-1,p.second,q-1,p.first.first,p.first.second);
    for(i=1;i<=n;i++) fa[i]=i,sz[i]=1;
    top=0;
    dfs(1,0,q-1,0);
    return 0;
}