[bzoj 3514] Codechef MARCH 14 GERALD 07 강화 판 링크 cut tree + 주석 트 리

꽤 오래된 구덩이 야.
우선 연결 블록 개수 = 총 포인트 - 공헌 이 있 는 변 수 를 고려 해 보 세 요. 즉, 링 이 형성 되 지 않 은 변 수 를 고려 해 보 세 요.
그러면 데이터 구조 문 제 를 사용 하 는 것 이 매우 전형 적 인 방법 입 니 다. pre [i] 는 변 i 가 가입 한 후에 어느 쪽 을 꺼 내야 하 는 지 표시 합 니 다.
오프라인 을 지원 한다 면 l 순 으로 bzoj 1878 처럼 매번 뛰 면 됩 니 다.
강제 온라인, 매번 질문 [l, r] 에서 pre [i] 가 [0, l - 1] 에서 의 변 수 를 주석 트 리 로 해결 합 니 다.
시한 이 너무 빡빡 하 다

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#define maxn 200010

using namespace std;

struct yts
{
	int x,y;
}e[maxn];

int pre[maxn],root[maxn],cnt[maxn*20],lch[maxn*20],rch[maxn*20];
bool rev[maxn*2];
int ch[maxn*2][2],fa[maxn*2],val[maxn*2],mn[maxn*2];
int n,m,tot,mx,typ,T;

int dir(int x)
{
	return x==ch[fa[x]][1];
}

int isroot(int x)
{
	return !((x==ch[fa[x]][0]) || (x==ch[fa[x]][1]));
}

int find_root(int x)
{
	while (fa[x]) x=fa[x];
	return x;
}

void reverse(int x)
{
	swap(ch[x][0],ch[x][1]);rev[x]^=1;
}

void push_down(int x)
{
	if (rev[x])
	{
		if (ch[x][0]) reverse(ch[x][0]);
		if (ch[x][1]) reverse(ch[x][1]);
		rev[x]=0;
	}
}

void push_up(int x)
{
	mn[x]=x;
	if (val[mn[ch[x][0]]]<val[mn[x]]) mn[x]=mn[ch[x][0]];
	if (val[mn[ch[x][1]]]<val[mn[x]]) mn[x]=mn[ch[x][1]];
}

void rotate(int x)
{
	int y=fa[x],z=fa[y],b=dir(x),a=ch[x][!b];
	if (!isroot(y))
	{
		int c=dir(y);ch[z][c]=x;
	}
	fa[x]=z;fa[y]=x;ch[x][!b]=y;ch[y][b]=a;
	if (a!=0) fa[a]=y;
	push_up(y);push_up(x);
}

void down(int x)
{
	if (!isroot(x)) down(fa[x]);
	push_down(x);
}

void splay(int x)
{
	down(x);
	while (!isroot(x))
	{
		int y=fa[x];
		if (isroot(y)) rotate(x);
		else
		{
			int b=dir(x),c=dir(y);
			if (b^c)
			{
				rotate(x);rotate(x);
			}
			else
			{
				rotate(y);rotate(x);
			}
		}
	}
}

void access(int x)
{
	for (int y=0;x;y=x,x=fa[x])
	{
		splay(x);
		ch[x][1]=y;
		push_up(x);
	}
}

void make_root(int x)
{
	access(x);
	splay(x);
	reverse(x);
}

void cut(int x,int y)
{
	make_root(x);
	access(x);
	splay(y);
	fa[y]=0;
}

void link(int x,int y)
{
	make_root(x);
	fa[x]=y;
}

int query(int x,int y)
{
	make_root(x);
	access(y);
	splay(y);
	return mn[y];
}

int modify(int pre,int l,int r,int x)
{
	int now=++tot;
	if (l==r)
	{
		lch[now]=rch[now]=0;cnt[now]=cnt[pre]+1;
	}
	else
	{
		int mid=(l+r)/2;
		if (x<=mid)
		{
			rch[now]=rch[pre];lch[now]=modify(lch[pre],l,mid,x);
		}
		else
		{
			lch[now]=lch[pre];rch[now]=modify(rch[pre],mid+1,r,x);
		}
		cnt[now]=cnt[lch[now]]+cnt[rch[now]];
	}
	return now;
}

int query(int root1,int root2,int l,int r,int x)
{
	if (r==x) return cnt[root2]-cnt[root1];
	int mid=(l+r)/2;
	if (x<=mid) return query(lch[root1],lch[root2],l,mid,x);
	else return cnt[lch[root2]]-cnt[lch[root1]]+query(rch[root1],rch[root2],mid+1,r,x);
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&T,&typ);
	for (int i=0;i<=n+m;i++) fa[i]=0,val[i]=m+1,mn[i]=i;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		e[i].x=x;e[i].y=y;
		if (x==y) {pre[i]=i;continue;}
		if (find_root(x)==find_root(y))
		{
			int t=query(x,y);
			pre[i]=val[t];
			cut(e[t-n].x,t);cut(e[t-n].y,t);
		}
		val[n+i]=i;mn[n+i]=n+i;
		link(x,n+i);link(y,n+i);
	}
	for (int i=1;i<=m;i++) root[i]=modify(root[i-1],1,m+1,pre[i]+1);
	int ans=0;
	while (T--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		if (typ) l^=ans,r^=ans;
		ans=n-query(root[l-1],root[r],1,m+1,l);
		printf("%d
",ans);
	}
	return 0;
}