题目概述

有 $n$ 个点 $m$ 条边，每条边有个出现时间 $s$ 和消失时间 $t$ ，问每个时刻是不是二分图。

解题报告

法老给我们上课用的PPT表示：把边加到线段树里然后线段树二分用LCT判奇环就好了。然后我就这么写了，成功TLE。

法老博客里的题解表示：只需要用LCT维护消失时间的最大生成树，然后用LCT判奇环就好了。

因为LCT只能维护森林所以一旦删除了一条边就会出现树边和非树边交替的情况，然后复杂度就成功的跪了。

所以我们需要用LCT维护消失时间的最大生成树，每次新加一条边的时候如果已经连通，就需要判断是否能够把原来连通路径上消失时间最小的那条边换掉，这样的话删除树边时就保证了覆盖这条树边的非树边早就删除了。

示例程序

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=300000,maxm=200000,maxt=100000;

int n,m,T,x[maxm+5],y[maxm+5],s[maxm+5],t[maxm+5],num,A[maxm+5],B[maxm+5],us[maxm+5];
int son[maxn+5][2],fa[maxn+5],si[maxn+5],MIN[maxn+5];bool flip[maxn+5],vis[maxt+5];

#define is_ro(p) ((p)!=son[fa[p]][0]&&(p)!=son[fa[p]][1])
#define Son(p) ((p)==son[fa[p]][1])
inline int Miner(int x,int y) {return !y||x&&t[x]<t[y]?x:y;}
inline void Pushup(int p){
    si[p]=si[son[p][0]]+(p<=n)+si[son[p][1]];
    MIN[p]=Miner(p>n?p-n:0,Miner(MIN[son[p][0]],MIN[son[p][1]]));
}
inline void Rotate(int t){
    int p=fa[t],d=Son(t)^1;son[p][d^1]=son[t][d];son[t][d]=p;
    Pushup(p);Pushup(t);if (!is_ro(p)) son[fa[p]][Son(p)]=t;
    if (son[p][d^1]) fa[son[p][d^1]]=p;fa[t]=fa[p];fa[p]=t;
}
inline void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;}
inline void Pushdown(int p) {if (flip[p]) flip[p]^=1,Addflip(son[p][0]),Addflip(son[p][1]);}
inline void Splay(int p){
    static int top,stk[maxn+5];stk[top=1]=p;;
    for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
        if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
}
inline void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);}
inline void Makero(int p) {Access(p);Splay(p);Addflip(p);}
inline void Link(int x,int y) {Makero(x);fa[x]=y;}
inline void Cut(int x,int y) {Makero(x);Access(y);Splay(y);fa[x]=son[y][0]=0;}
inline int getfa(int x) {Access(x);Splay(x);while (son[x][0]) x=son[x][0];return x;}
inline int Size(int x,int y) {Makero(x);Access(y);Splay(x);return si[x];}
inline int Min(int x,int y) {Makero(x);Access(y);Splay(x);return MIN[x];}
inline bool Scmp(const int &a,const int &b) {return s[a]<s[b];}
inline bool Tcmp(const int &a,const int &b) {return t[a]<t[b];}
inline void Insert(int i){
    if (x[i]==y[i]) {us[i]=1;num++;return;}
    if (getfa(x[i])==getfa(y[i])){
        if (Size(x[i],y[i])&1) num++,us[i]=1; else us[i]=2;int j=Min(x[i],y[i]);
        if (t[j]<t[i]) Cut(x[j],j+n),Cut(y[j],j+n),Link(x[i],i+n),Link(y[i],i+n),us[j]=us[i],us[i]=0;
    } else Link(x[i],i+n),Link(y[i],i+n);
}
inline void Delete(int i) {if (!us[i]) Cut(x[i],i+n),Cut(y[i],i+n); else num-=us[i]<2;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&T);for (int i=1;i<=n;i++) si[i]=1;
    for (int i=1;i<=m;i++) scanf("%d%d%d%d",&x[i],&y[i],&s[i],&t[i]);
    for (int i=1;i<=m;i++) A[i]=B[i]=i,MIN[i+n]=i;sort(A+1,A+1+m,Scmp);sort(B+1,B+1+m,Tcmp);
    for (int i=0,j=1,k=1;i<=T;vis[i++]=num>0)
        {while (j<=m&&s[A[j]]<=i) Insert(A[j++]);while (k<=m&&t[B[k]]<=i) Delete(B[k++]);}
    for (int i=0;i<T;i++) vis[i]?puts("No"):puts("Yes");return 0;
}