题目链接

题面：

题解：
一直也没用LCT写过题，这算是LCT写的第一个题了吧。

我们用LCT维护一个删边时间最大的生成树。
对于某一时刻在图中而不在树中的边我们开个数组标记一下。并开个变量记录一下奇环的数量。

插入一条边时，若插入后不会成环则直接插入。如插入后会成环，则把环中的删除时间最早的边在LCT中删除，插入当前边（如果当前边是删除时间最早的，那么不删除不插入），标记所删除的边，并维护奇环的数量。

删除一条边时，先检查是否是已标记的边。如果不是已标记的边，则在LCT中将这条边删除。否则修改标记并维护奇环的数量。

由于直接维护边不太好维护，我们把 m 条边看作 m个点进行维护。

那么就是维护总共有 n+m 的 LCT。
在统计删除时间最早 和 是奇环还是偶环等信息时，只维护由边转化过来的点即可。

代码：
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)，但是有点常数，仅比两个 l o g log log 的线段树分治快一点点。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=300100;
const int maxp=800100;
const int maxm=1000100;
const int up=200000;

struct tree
{
    int son[2];
    int fa,minn,si,rev;
}t[maxn];

int st[maxn];
int deltime[maxn],isdel[maxn];
int n,m,k,cnt=0;
int idin[maxn];

struct node
{
    int x,y;
    int begintime,endtime;
    int id;
}in[maxn],out[maxn];

bool cmpin(const node &a,const node &b)
{
    return a.begintime<b.begintime;
}
bool cmpout(const node &a,const node &b)
{
    return a.endtime<b.endtime;
}

void pushup(int x)
{
    t[x].minn=x;
    t[x].si=x>n;
    if(t[x].son[0])
    {
        t[x].si+=t[t[x].son[0]].si;
        t[x].minn=deltime[t[x].minn]<deltime[t[t[x].son[0]].minn]?t[x].minn:t[t[x].son[0]].minn;
    }
    if(t[x].son[1])
    {
        t[x].si+=t[t[x].son[1]].si;
        t[x].minn=deltime[t[x].minn]<deltime[t[t[x].son[1]].minn]?t[x].minn:t[t[x].son[1]].minn;
    }
}

void _reverse(int x)
{
    if(!x) return ;
    swap(t[x].son[0],t[x].son[1]);
    t[x].rev^=1;
}

void pushdown(int x)
{
    if(!x) return ;
    if(t[x].rev)
    {
        _reverse(t[x].son[0]);
        _reverse(t[x].son[1]);
        t[x].rev=0;
    }
}

bool notroot(int x)
{
    return t[t[x].fa].son[0]==x||t[t[x].fa].son[1]==x;
}

int get_son(int x)
{
    return x==t[t[x].fa].son[1];
}

void rot(int x)
{
    int y=t[x].fa,z=t[y].fa;
    int k=get_son(x),w=t[x].son[k^1];
    t[y].son[k]=w,t[w].fa=y;

    if(notroot(y))t[z].son[get_son(y)]=x;
    t[x].fa=z;

    t[x].son[k^1]=y,t[y].fa=x;
    pushup(y),pushup(x);
}

void splay(int x)
{
    int top=0;
    st[++top]=x;
    for(int pos=x;notroot(pos);pos=t[pos].fa) st[++top]=t[pos].fa;
    while(top) pushdown(st[top--]);

    while(notroot(x))
    {
        int y=t[x].fa;
        int z=t[y].fa;
        if(notroot(y))
            if(get_son(x)==get_son(y)) rot(y);
            else rot(x);
        rot(x);
    }
}

void access(int x)
{
    for(int y=0;x;y=x,x=t[x].fa)
    {
        splay(x);
        t[x].son[1]=y;
        pushup(x);
    }
}

void makeroot(int x)
{
    access(x);
    splay(x);
    _reverse(x);
}

int findroot(int x)
{
    access(x);
    splay(x);
    while(t[x].son[0]) pushdown(x),x=t[x].son[0];
    splay(x);
    return x;
}

void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}

bool link(int x,int y)
{
    makeroot(x);
    if(findroot(y)==x) return false;
    t[x].fa=y;
    return true;
}

bool cut(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x||t[y].fa!=x||t[y].son[0]) return false;
    t[y].fa=t[x].son[1]=0;
    pushup(x);
    return true;
}

bool connected(int x,int y)
{
    x=findroot(x);
    y=findroot(y);
    return x==y;
}

//拉出x-y 链，其中y现在为根节点且只有左子树
void ***(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}

void _insert(int p)
{
    deltime[in[p].id]=in[p].endtime;
    t[in[p].id].minn=in[p].id;
    int x=in[p].x,y=in[p].y,id=in[p].id;
    if(connected(x,y))
    {
        ***(x,y);
        if(deltime[t[y].minn]>deltime[id])
        {
            if(t[y].si%2==0)
                isdel[id]=2,cnt++;
            else isdel[id]=1;
        }
        else
        {
            if(t[y].si%2==0)
                isdel[t[y].minn]=2,cnt++;
            else isdel[t[y].minn]=1;

            int de=t[y].minn;
            cut(in[idin[de]].x,de);
            cut(in[idin[de]].y,de);
            link(x,id);
            link(y,id);
        }
    }
    else
    {
        link(in[p].x,in[p].id);
        link(in[p].y,in[p].id);
    }
}

void del(int p)
{
    if(isdel[out[p].id])
    {
        if(isdel[out[p].id]==2) cnt--;
        isdel[out[p].id]=0;
    }
    else
    {
        cut(out[p].x,out[p].id);
        cut(out[p].y,out[p].id);
    }
}

int main(void)
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        deltime[i]=inf;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&in[i].x,&in[i].y,&in[i].begintime,&in[i].endtime);
        in[i].id=i+n;
        out[i]=in[i];
    }
    sort(in+1,in+m+1,cmpin);
    sort(out+1,out+m+1,cmpout);
    for(int i=1;i<=m;i++)
        idin[in[i].id]=i;

    int cntin=1,cntout=1;
    for(int i=0;i<k;i++)
    {
        while(cntin<=m&&in[cntin].begintime<=i)
            _insert(cntin++);
        while(cntout<=m&&out[cntout].endtime<=i)
            del(cntout++);
        if(!cnt) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}