题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4025
线段树分治，用 LCT 维护链的长度即可。不过很慢。
正常（更快）的方法应该是线段树分治+并查集（按秩合并，链长可以暴力爬）或者 LCT 维护删除时间最大生成树。就不写了。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ls Ls[cr] #define rs Rs[cr] #define lc c[x][0] #define rc c[x][1] #define pb push_back using namespace std; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } const int N=1e5+5,M=2e5+5; int n,m,fa[N],c[N][2],rev[N],siz[N],stk[N],tp; int tot,Ls[M],Rs[M],top; struct Node{int x,y;Node(int x=0,int y=0):x(x),y(y) {} }sta[N]; vector<Node> vt[M];void build(int l,int r,int cr) {if(l==r)return; int mid=l+r>>1;ls=++tot; build(l,mid,ls);rs=++tot; build(mid+1,r,rs); } void ins(int l,int r,int cr,int L,int R,Node k) {if(l>=L&&r<=R){vt[cr].pb(k);return;}int mid=l+r>>1;if(L<=mid)ins(l,mid,ls,L,R,k);if(mid<R)ins(mid+1,r,rs,L,R,k); }bool isrt(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;} void pshp(int x){siz[x]=siz[lc]+siz[rc]+1;} void Rev(int x){if(rev[x]){rev[x]=0;rev[lc]^=1;rev[rc]^=1;swap(lc,rc);}} void rotate(int x) {int y=fa[x],z=fa[y],d=(x==c[y][1]);if(!isrt(y))c[z][y==c[z][1]]=x;fa[x]=z;fa[y]=x; fa[c[x][!d]]=y;c[y][d]=c[x][!d]; c[x][!d]=y;pshp(y); pshp(x); } void splay(int x) {stk[tp=1]=x;for(int k=x;!isrt(k);k=fa[k])stk[++tp]=fa[k];for(int i=tp;i;i--)Rev(stk[i]);int y,z;while(!isrt(x)){y=fa[x]; z=fa[y];if(!isrt(y))( (x==c[y][0])^(y==c[z][0]) )?rotate(x):rotate(y);rotate(x);} } void access(int x) {for(int t=0;x;splay(x),rc=t,pshp(x),t=x,x=fa[x]); } void mkrt(int x) {access(x); splay(x); rev[x]^=1; } void split(int x,int y) {mkrt(x); access(y); splay(y); } bool link(Node k) {int x=k.x, y=k.y; split(x,y);int cr=y; while(c[cr][0])cr=c[cr][0];if(cr==x) return (siz[y]&1);sta[++top]=k; fa[x]=y; return false; } void cut(Node k) {int x=k.x, y=k.y; split(x,y);c[y][0]=fa[x]=0; pshp(y); } void solve(int l,int r,int cr) {int sz=vt[cr].size(); bool flag=0;for(int i=0;i<sz;i++){flag=link(vt[cr][i]); if(flag)break;}if(flag){for(int i=l;i<=r;i++)puts("No");return;}if(l==r){puts("Yes");return;}int mid=l+r>>1,nw=top;solve(l,mid,ls); for(int& i=top;i>nw;i--)cut(sta[i]);solve(mid+1,r,rs); for(int& i=top;i>nw;i--)cut(sta[i]); } int main() {n=rdn();int T=rdn();m=rdn();tot=1;build(1,m,1);for(int i=1;i<=n;i++)siz[i]=1;for(int i=1,u,v,st,en;i<=T;i++){u=rdn();v=rdn();st=rdn()+1;en=rdn();ins(1,m,1,st,en,Node(u,v));}solve(1,m,1); return 0; }
