题目链接：戳我

【线段树分治版本代码】

这里面的线段树是时间线段树，每一个节点都要开一个vector，记录当前时间区间中存在的边的标号qwq

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<map>

#include<stack>

#include<vector>

#define MAXN 1000010

using namespace std;

int n,m;

int fa[MAXN],siz[MAXN],tim[5010][5010];

struct Node{int x,y;};

struct Que{int op,x,y;}q[MAXN];

struct Seg{

    int l,r;

    vector<int>v;

}t[MAXN<<2];

stack<Node>s;

//map<pair<int,int>,int>tim;

inline int ls(int x) {return x<<1;}

inline int rs(int x) {return x<<1|1;}

inline int find(int x){return fa[x]==x?x:find(fa[x]);}

inline void build(int x,int l,int r)

{

    t[x].l=l,t[x].r=r;

    if(l==r) return;

    int mid=(l+r)>>1;

    build(ls(x),l,mid);

    build(rs(x),mid+1,r);

}

inline void merge(int x,int y)

{

    x=find(x),y=find(y);

    if(x==y) return;

    if(siz[x]>siz[y]) swap(x,y);

    fa[x]=y;

    s.push((Node){x,y});

    siz[y]+=siz[x];

}

inline void del(int x)

{

    while((int)s.size()>x)

    {

        Node cur=s.top(); s.pop();

        siz[cur.y]-=siz[fa[cur.x]=cur.x];

    }

}

inline void insert(int x,int ll,int rr,int k)

{

    int l=t[x].l,r=t[x].r;

    if(ll<=l&&r<=rr)

    {

        t[x].v.push_back(k);

        return;

    }

    int mid=(l+r)>>1;

    if(ll<=mid) insert(ls(x),ll,rr,k);

    if(mid<rr) insert(rs(x),ll,rr,k);

}

inline void solve(int x)

{

    int cur=s.size();

    for(int i=0,len=t[x].v.size();i<len;i++)

        merge(q[t[x].v[i]].x,q[t[x].v[i]].y);

    if(t[x].l==t[x].r)

    {

        if(q[t[x].l].op==2)

        {

            if(find(q[t[x].l].x)==find(q[t[x].l].y))

                printf("Y\n");

            else printf("N\n");

        }

    }

    else solve(ls(x)),solve(rs(x));

    del(cur);

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    //freopen("ce.out","w",stdout);

    #endif

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;

    build(1,1,m);

    for(int i=1;i<=m;i++)

    {

        int op,x,y;

        scanf("%d%d%d",&op,&x,&y);

        if(x>y) swap(x,y);

        q[i]=(Que){op,x,y};

        if(op==1)

        {

            insert(1,tim[x][y],i,i);

            tim[x][y]=0;

        }

        else if(op==0) tim[x][y]=i;

    }

    for(int i=1;i<=n;i++)

        for(int j=i;j<=n;j++)

            if(tim[i][j])

                insert(1,tim[i][j],m,tim[i][j]);

    solve(1);

    return 0;

}

请不要用map！！！会T死的！！！

【LCT版本代码】（咕咕咕）

强制在线的还不会写。。暂且也咕着吧qwqwq