【2022NOIP模拟赛20】小Z的作业 做题记录

有 $n$ 个点，给定 $m$ 条有顺序的无向边和一个 $k$。

$q$ 次询问，每次询问给定一个区间 $[l_i,r_i]$，问应用区间内的边后连通块个数是否 $\le k$。

询问相互独立，强制在线。

$1\le n,m\le 2\times 10^5$，$1\le k\le n$，$1\le q\le 5\times 10^5$。

考虑求出 $f_r$ 表示最大的使得 $[f_r,r]$ 合法的左端点。

一个朴素的做法是扫描线，用 LCT 维护。

但是我们不会 LCT。

注意到双指针过程中左端点 $l$ 扫过的边 $(x_p,y_p)$ 会对 $f_{[p,n]}$ 有贡献，而由于 $f_{[r+1,n]}$ 都不需要这条边，所以只会对 $f_{[p,r]}$ 有贡献。

这种一个操作对某个区间有贡献的情况，不妨考虑线段树分治。

不同于一般情况，在本题中线段树分治的同时会加入新的操作，所以本题的线段树分治是半在线的。

具体的，线段树分治时维护一个并查集：

• 先分治右边再分治左边；
• 若当前点是叶子，则先令 $f_l=f_{l+1}$，然后不断往左推 $f_l$ 直到合法；
• 在推的过程中，在并查集中加入新的边，并把新的边 $(x_p,y_p)$ 加入区间 $[p,l-1]$；
• 在 return 之前清空并查集中在当前节点新加入的所有边；

代码如下：

void slove(int u,int l,int r)
{
	int tp=top;
	for(int x:idx[u]) meg(rx[x],ry[x]);
	if(l==r)
	{
		f[l]=f[l+1];
		while(f[l]>1&&cnt>K)
		{
			f[l]--;
			meg(rx[f[l]],ry[f[l]]);
			add(1,1,m,f[l],l-1,f[l]);
		}
		if(cnt>K&&f[l]>=1) f[l]=0;
	}
	else
	{
		int mid=l+r>>1;
		slove(u<<1|1,mid+1,r);
		slove(u<<1,l,mid);
	}
	rolbak(tp);
}

由于 $l\not\in[p,l-1]$，所以从 $l$ 去到 $l-1$ 的过程中一定会经过 $[p,l-1]$ 拆分出的线段树上的节点，所以直接清空并查集中在当前节点新加入的所有边是没有问题的。

时间复杂度 $O(m\log m\log n)$（$\log n$ 来自并查集），完整代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=200005;

int n,m,K,tp;
int rx[S],ry[S];
int cnt,fa[S],hei[S];
int top,fap[S],fax[S],hip[S],hix[S],ctx[S];
vector<int> idx[S<<2];
int f[S];
int q;

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

inline void meg(int x,int y)
{
	int rx=fnd(x),ry=fnd(y);
	if(hei[rx]>hei[ry]) swap(rx,ry);
	if(rx!=ry)
	{
		top++;
		fap[top]=rx,fax[top]=rx;
		hip[top]=ry,hix[top]=hei[ry];
		ctx[top]=cnt;
		fa[rx]=ry;
		hei[ry]=max(hei[ry],hei[rx]+1);
		cnt--;
	}
}

inline void rolbak(int tme)
{
	while(top>tme)
	{
		fa[fap[top]]=fax[top];
		hei[hip[top]]=hix[top];
		cnt=ctx[top];
		top--;
	}
}

void add(int u,int l,int r,int L,int R,int x)
{
	if(l>R||r<L) return;
	if(l>=L&&r<=R) return idx[u].push_back(x),void();
	int mid=l+r>>1;
	if(L<=mid) add(u<<1,l,mid,L,R,x);
	if(R>=mid+1) add(u<<1|1,mid+1,r,L,R,x);
}

void slove(int u,int l,int r)
{
	int tp=top;
	for(int x:idx[u]) meg(rx[x],ry[x]);
	if(l==r)
	{
		f[l]=f[l+1];
		while(f[l]>1&&cnt>K)
		{
			f[l]--;
			meg(rx[f[l]],ry[f[l]]);
			add(1,1,m,f[l],l-1,f[l]);
		}
		if(cnt>K&&f[l]>=1) f[l]=0;
	}
	else
	{
		int mid=l+r>>1;
		slove(u<<1|1,mid+1,r);
		slove(u<<1,l,mid);
	}
	rolbak(tp);
}

int main()
{
	freopen("darkduck.in","r",stdin);
	freopen("darkduck.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&K,&tp);
	for(int i=1;i<=m;i++) scanf("%d%d",&rx[i],&ry[i]);
	cnt=n;
	for(int i=1;i<=n;i++) fa[i]=i,hei[i]=1;
	f[m+1]=m+1;
	slove(1,1,m);
	scanf("%d",&q);
	unsigned lans=0;
	for(int i=1;i<=q;++i)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		if(tp==1)
		{
			l=(l+lans)%m+1;
			r=(r+lans)%m+1;
			if(l>r) swap(l,r);
		}
		bool fl=l<=f[r];
		puts(fl?"Yes":"No");
		lans<<=1;
		if(fl) ++lans;
	}
	return 0;
}