自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:33:35，当前版本为作者最后更新于2021-08-04 17:50:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意：问区间能最少划分成段，每一段 2-SAT 判断为 $1$。

10~40pts

很明显需要维护一个 $f$ 数组，$f_i=k$ 代表 $[i,k]$ 这段区间非法且 $k$ 最小，然后用倍增跳。直接对于每个 $i$ 暴力求出 $f_i$ 即可。
求的方法是用 2-SAT，每次 $u\rightarrow v,v\rightarrow u,u'\rightarrow v',v'\rightarrow u'$。
当然由于连的是双向边可以把 tarjan 换成并查集。

100pts

进行分析，发现 $f$ 数组具有决策单调性。简要证明一下：我们考虑从右往左看，每次会新加入一条边，也就更有可能在更近的地方非法，而且不可能在更远的地方达到第一个非法点，所以 $f_i\le f_j(i<j)$。二分单调队列/单调栈很明显不好维护这个信息，我们考虑用整体二分去求。
定义 $cal(l,r,L,R)$ 代表当前是 $l,r$ 区间，$f_i\in [L,R](i\in [l,r])$。递归时往 $cal(l,mid-1,L,f_{mid})$ 和 $cal(mid+1,r,f_{mid},R)$ 这样就可以用一个并查集进行撤销和继承。
求 $f_{mid}$ 的时候从 $L$ 开始一直加边，加到非法为止。注意有可能加到末尾依然合法，需要特判。
非法的判定可以用加边后 $u,u'$ 是否连通来判断。考虑反证法，若存在 $w,w'$ 在加边后连通，且 $u,u'$ 不连通，那么 $w,w'$ 分别与 $u$ 和 $v$ 或者 $u'$ 和 $v'$ 连通。根据我们的连边方式，若 $u,v$ 连通则 $u',v'$ 连通。所以 $u,u'$ 连通。
时间复杂度 $O(m\log m\log n+q\log m)$。具体实现可以看代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=6e5+5,maxm=1e5+5;
char __buf[1<<21],*__p1,*__p2;
#define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<21,stdin),__p1==__p2?EOF:*__p1++):*__p1++)
inline int read() {
	int __x=0;
	char __c=getchar();
	while(__c<'0'||__c>'9') __c=getchar();
	while(__c>='0'&&__c<='9') {
		__x=__x*10+__c-'0';
		__c=getchar();
	}
	return __x;
}
inline char pc(char ch,bool bj) {
	static char buf[1<<18],*p1=buf,*p2=buf+(1<<18);
	return ((bj)||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
void print(int x) {
	if(x<0)x=-x,pc('-',0);
	if(x>9)print(x/10);
	pc(x%10^48,false);
}
inline void printnum(int x,int ch) {
	print(x),pc(ch,false);
}
struct oper {
	int op,x,y;
	oper() {}
	oper(int Op,int X,int Y) {
		op=Op,x=X,y=Y;
	}
} o[maxn*4];
int u[maxn],v[maxn],oc,n,m,ans[maxn],f[maxm*2],siz[maxm*2],q,g[maxn][20],zm[maxn];
int getf(int x) {
	return f[x]==x?x:getf(f[x]);
}
int opp(int x) {
	return x&1?x+1:x-1;
}
void merge(int x,int y) {
	x=getf(x),y=getf(y);
	if(x==y)return;
	if(siz[x]<siz[y])swap(x,y);
	o[++oc]=oper(0,y,0),f[y]=x;
	o[++oc]=oper(1,x,siz[y]),siz[x]+=siz[y];
}
void replace(int cas) {
	while(oc>cas) {
		int op=o[oc].op,x=o[oc].x,y=o[oc].y;
		if(!op)f[x]=x;
		if(op==1)siz[x]-=y;
		oc--;
	}
}
bool check(int x) {
	return getf(x)==getf(opp(x));
}
void solve(int l,int r,int L,int R,bool lst) {
	if(L==R) {
		for(register int i=l; i<=r; i++)ans[i]=L;
		return;
	}
	if(l>r)return;
	int mid=(l+r)/2,cas=oc;
	bool now=lst;
	for(register int i=mid; i<=r&&i<L; i++) {
		merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
		now|=check(u[i]);
		if(now)break;
	}//mid~min(r,L-1) 的边是一定要用的，先加上
	int tmp=oc,sum=now;
	for(register int i=max(L,mid); i<=R; i++) {
		merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
		now|=check(u[i]);
		if(now) {
			ans[mid]=i;
			break;
		}
	}//从 max(L,mid) 一直加到 R 来寻找 mid 处答案
	bool pd=0;
	if(!ans[mid]) {
		ans[mid]=m+1;
		for(register int i=mid+1; i<=r; i++)ans[i]=m+1;
		pd=1;
	}//如果到最右边仍然合法，那么它的右区间也合法
	replace(tmp);
	solve(l,mid-1,L,ans[mid],sum);//l~mid-1 需要 mid~min(r,L-1) 的边
	replace(cas);
	if(pd)return;
	now=lst;
	for(register int i=max(r+1,L); i<ans[mid]; i++) {
		merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
		now|=check(u[i]);
		if(now)break;
	}
	solve(mid+1,r,ans[mid],R,now);//mid+1,~r 需要 max(r+1,L)~ans[mid]-1 的边
	replace(cas);
}
int main() {
	int U,x,V,y;
	bool p=0;
	n=read(),m=read(),q=read();
	for(register int i=1; i<=2*n; i++)f[i]=i,siz[i]=1;
	for(register int i=1; i<=m; i++) {
		U=read(),x=read(),V=read(),y=read();
		zm[i]=zm[i-1]+(U==V&&x!=y);
		u[i]=U*2-1+x,v[i]=V*2-1+y;
		merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
		p|=check(u[i]);
	}
	if(!p) {
		while(q--)printnum(1,'\n');
		return pc(0,1),0;
	}
	replace(0);
	u[m+1]=1,v[m+1]=2;
	solve(1,m,1,m+1,0);
	for(register int i=0; i<20; i++)g[m+1][i]=m+1;
	for(register int i=m; i; i--) {
		g[i][0]=ans[i];
		for(register int j=1; j<20; j++)g[i][j]=g[g[i][j-1]][j-1];
	}
	while(q--) {
		x=read(),y=read();
		if(zm[y]-zm[x-1]>0) {
			printnum(-1,'\n');
			continue;
		}
		int w=1;
		for(register int i=19; i>=0; i--)
			if(g[x][i]<=y)x=g[x][i],w+=(1<<i);
		printnum(w,'\n');
	}
	pc(0,1);
	return 0;
}