题目链接

题面：

题解：
线段树分治。
（1）有一些操作，每个操作只在 l − r l-r l−r 的时间段内有效。
（2）有一些询问，每个询问询问某一个时间点所有操作的贡献。

离线，时间线段树上维护按秩合并可撤销并查集。
时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

代码：

#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=500100;
const int maxp=800100;
const int maxm=1000100;
const int up=200000;

int f[maxn],d[maxn],top=0;
pair<int,int>st[maxn];

struct tree
{
    int l,r;
    vector<pair<int,int> >vc;
}t[maxn<<2];

struct node
{
    int x,y,id;
    node(){}
    node(int a,int b,int c)
    {
        x=a,y=b,id=c;
    }
};

vector<node>vc[maxn];
int ans[maxn];
map<pair<int,int>,int>mp;

int fi(int x)
{
    if(f[x]==x) return x;
    else return fi(f[x]);
}

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].vc.clear();
    if(l==r) return ;
    build(l,tmid,lc);
    build(tmid+1,r,rc);
}

void change(int l,int r,int cnt,pair<int,int> val)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        t[cnt].vc.pb(val);
        return ;
    }
    if(t[lc].r>=l) change(l,r,lc,val);
    if(t[rc].l<=r) change(l,r,rc,val);
}

void _merge(int x,int y)
{
    int xx=fi(x),yy=fi(y);
    if(xx==yy) return ;
    if(d[xx]>d[yy]) swap(xx,yy);
    st[++top]=pr(xx,d[xx]==d[yy]);
    f[xx]=yy;
    d[yy]+=(d[xx]==d[yy]);
}

void dfs(int l,int r,int cnt)
{
    int now=top;
    for(int i=0;i<t[cnt].vc.size();i++)
        _merge(t[cnt].vc[i].first,t[cnt].vc[i].second);
    if(l==r)
    {
        for(int i=0;i<vc[l].size();i++)
        {
            int xx=fi(vc[l][i].x),yy=fi(vc[l][i].y);
            if(xx==yy)
                ans[vc[l][i].id]=1;
        }
    }
	else
	{
		dfs(l,tmid,lc);
    	dfs(tmid+1,r,rc);
	}
    while(top>now)
    {
        d[f[st[top].first]]-=st[top].second;
        f[st[top].first]=st[top].first;
        top--;
    }
}


int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        f[i]=i,d[i]=1;
    build(1,m,1);
    int op,x,y;
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(x>y) swap(x,y);
        if(op==0)
        {
            mp[pr(x,y)]=i;
        }
        else if(op==1)
        {
            int pos=mp[pr(x,y)];
            mp.erase(pr(x,y));
            change(pos,i-1,1,pr(x,y));
        }
        else if(op==2)
        {
            vc[i].pb(node(x,y,++tot));
        }
    }
    for(auto p : mp)
        change(p.second,m,1,pr(p.first.first,p.first.second));

    dfs(1,m,1);

    for(int i=1;i<=tot;i++)
    {
        if(ans[i]) printf("Y\n");
        else printf("N\n");
    }
    return 0;
}