题解
线段树分治的板子题。
根据时间加边与删边，如果直接维护这个图的话明显会T，当然只加边的画不会，但由于会删边，我们每次判图都必须跑一遍这个图，于是就需要 ，明显会T，于是就要用线段树分治来维护每个时间上的边。
我们建一棵树来维护每个时间的图，从根到叶子的链上构成的图就是叶子这个时间节点的图的状态。每次删边时，就在这条边存在的时间区间上加上这条边。这样就可以维护任意时间点的图，保证我们到任意点时只会有加边的操作，不会去删边。
至于如何判断二分图，我们在点上都是维护了一个只有加边动态图的，如果回溯的话只需要撤销最后加的那一条边。我们用一个带权并查集去维护这个图，而并查集维护的图又一定是一棵树，而加一条边是可以 解决的。为了避免卡并查集，还需要按秩合并去保证树高。
插入边时若这条边连接了两棵未连接的树，明显不会有关系，可如果形成了奇环的话那就肯定不是二分图了，而判奇环就只需要维护每个点的深度。
于是，就可以过这题了。
源码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
typedef long long LL;
#define lson rt<<1
#define rson rt<<1|1
typedef pair<int,int> pii;
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
struct edge{int u,v;edge(int U,int V):u(U),v(V){}};
struct piar{int x,y;piar(int X,int Y):x(X),y(Y){}};
int n,q,L[MAXN<<2],R[MAXN<<2],ans[MAXN];
vector<edge> tag[MAXN<<2];
map<int,int> g[MAXN];
int fa[MAXN],siz[MAXN],dis[MAXN];
void build(int rt,int l,int r){
L[rt]=l;R[rt]=r;if(l==r)return ;int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
}
void query(int rt,int l,int r,const edge &E){
if(L[rt]>r||R[rt]<l)return ;
if(l<=L[rt]&&R[rt]<=r)return (void)(tag[rt].push_back(E));
query(lson,l,r,E);query(rson,l,r,E);
}
int findFa(int x){while(fa[x]!=x)x=fa[x];return x;}
int getdis(int x){int res=0;while(fa[x]!=x)res^=dis[x],x=fa[x];return res;}
int solve(int x,int y,stack<piar> &sta){
int dx=getdis(x),dy=getdis(y);
x=findFa(x);y=findFa(y);
if(x==y)return dx^dy;
if(siz[x]>siz[y])swap(x,y),swap(dx,dy);
siz[y]+=siz[x];fa[x]=y;dis[x]=dx^dy^1;
sta.push(piar(x,y));return 1;
}
void delet(piar p){int x=p.x,y=p.y;siz[y]-=siz[x];dis[fa[x]=x]=0;}
void dfs(int rt,int fg){
stack<piar> sta;
for(auto e:tag[rt])fg&=solve(e.u,e.v,sta);
if(L[rt]==R[rt])ans[L[rt]]=fg;
else dfs(lson,fg),dfs(rson,fg);
while(!sta.empty()){delet(sta.top());sta.pop();}
}
signed main(){
read(n);read(q);build(1,1,q);
for(int i=1;i<=q;i++){
int x,y;read(x);read(y);
if(!g[x][y])g[x][y]=i;
else query(1,g[x][y],i-1,edge(x,y)),g[x][y]=0;
}
for(int i=1;i<=n;i++){
siz[fa[i]=i]=1;
for(auto p:g[i])if(p.second>0)
query(1,p.second,q,edge(i,p.first));
}
dfs(1,1);
for(int i=1;i<=q;i++)puts(ans[i]?"YES":"NO");
return 0;
}
谢谢！！！ | 
转播
