LOJ，T了。
#pragma GCC optimize(3) #include<bits/stdc++.h> #define maxn 500005 #define pb push_back #define lc u<<1 #define rc u<<1|1 using namespace std; char cb[1<<15],*cs=cb,*ct=cb; #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++) void read(int &res){ char ch; for(;!isdigit(ch=getc());); for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); } int n,m,K,x[maxn],y[maxn],rx[maxn],ry[maxn],F[maxn],siz[maxn],ans[maxn],tim[maxn],c[maxn],pos[maxn],cnt,qcnt; int Find(int u){ return !F[u] ? u : Find(F[u]); } vector<int>lid[maxn<<2]; inline bool cmp(const int &u,const int &v){ return x[u] == x[v] ? y[u] == y[v] ? u < v : y[u] < y[v] : x[u] < x[v]; } void Insert(int u,int l,int r,int ql,int qr,int v){ if(l>qr || ql>r || ql>qr) return; if(ql<=l && r <= qr){ lid[u].pb(v); return; } int mid = (l+r) >> 1; Insert(lc,l,mid,ql,qr,v),Insert(rc,mid+1,r,ql,qr,v); } void dfs(int u,int l,int r){ if(l>r) return; for(int v:lid[u]){ int &a = rx[v] = Find(x[v]) , &b = ry[v] = Find(y[v]); if(a==b) continue; if(siz[a] > siz[b]) swap(a,b); F[a] = b , siz[b] += siz[a]; } int mid = (l+r) >> 1; if(l==r) puts(Find(x[pos[l]]) == Find(y[pos[l]]) ? "Y" : "N"); else dfs(lc,l,mid),dfs(rc,mid+1,r); for(int v=lid[u].size()-1;v>=0;v--){ int a = rx[lid[u][v]] , b = ry[lid[u][v]]; if(a == b) continue; F[a] = 0 , siz[b] -= siz[a]; } } int main(){ read(n),read(m); qcnt = 0; for(int i=1,op;i<=m;i++){ read(op),read(x[i]),read(y[i]); if(x[i] > y[i]) swap(x[i],y[i]); if(op == 2) pos[++qcnt] = i; else c[++cnt] = i , tim[i] = qcnt; } sort(c+1,c+1+cnt,cmp); for(int i=2;i<=cnt+1;) if(x[c[i]] == x[c[i-1]] && y[c[i]] == y[c[i-1]]) Insert(1,1,qcnt,tim[c[i-1]]+1,tim[c[i]],c[i-1]),i+=2; else Insert(1,1,qcnt,tim[c[i-1]]+1,qcnt,c[i-1]),i++; dfs(1,1,qcnt); }