CF1217F - Forced Online Queries Problem

Posted on Edited on In

CF1217F - Forced Online Queries Problem

题目大意

\(n\) 个点无向图， \(m\) 次操作，每次加入/删除一条边，或者查询两个点连通性

\(lst\) 为上次查询的连通性情况，即 \(lst=\{0,1\}\)

加密方式为 \(x=(x'+lst-1)\mod n+1\)


吐槽

如果你管这叫Forced Online？


分析

无强制在线

如果没有这个假的强制在线，考虑用线段树分治解决

预处理每条边出现的时间区间 \([L,R]\) ，加入线段树，用按秩合并并查集维护加边和回撤即可


伪强制在线

依然是预处理每条边的时间区间

虽然我们无法确定一条边存在的时间区间

但是我们可以确定一条边可能存在，或者说可能被修改的时间区间

一次修改对应两条可能的边，对于两种可能都加入两条边对应的时间节点

每次加边修改指定边，对于涉及的两条边，修改之后判断是否存在

然后对于存在的边，将这条边从现在开始到 下一个时间节点 出现之间都插入即可

注意这个线段树分治是"半在线"的，即要一边处理操作一边插入修改

由于修改的区间和目前遍历的区间不交，所以容易实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
const int N=2e5+10;

int n,m,c;
map <int,int> M[N],I[N];
vector <int> T[N*2];
int P[N*2];


int stk[N],top,S[N],F[N];
int Find(int x){
	while(F[x]!=x) x=x[F][F];
	return x;
}
void Union(int x,int y){
	x=Find(x),y=Find(y);
	if(x==y) return;
	if(S[x]>S[y]) swap(x,y);
	F[x]=y,S[y]+=S[x],stk[++top]=x;
}
void Back(){
	int x=stk[top--];
	S[F[x]]-=S[x],F[x]=x;
}

vector <Pii> G[N<<2];
void Add(int p,int l,int r,int ql,int qr,Pii x){
	if(ql>qr) return;
	if(ql<=l && r<=qr) return G[p].pb(x);
	int mid=(l+r)>>1;
	if(ql<=mid) Add(p<<1,l,mid,ql,qr,x);
	if(qr>mid) Add(p<<1|1,mid+1,r,ql,qr,x);
}
int opt[N],A[N],B[N],lst;
void Solve(int p,int l,int r){
	int tmp=top;
	for(Pii t:G[p]) Union(t.first,t.second);
	if(l==r) {
		int x=(A[l]+lst-1)%n+1;
		int y=(B[l]+lst-1)%n+1;
		if(x>y) swap(x,y);
		if(opt[l]==1) {
			M[x][y]^=1;
			rep(i,0,1) {
				int x=(A[l]+i-1)%n+1;
				int y=(B[l]+i-1)%n+1;
				if(x>y) swap(x,y);
				int id=I[x][y];
				P[id]++;
				if(M[x][y]) Add(1,1,m,l+1,T[id][P[id]]-1,mp(x,y));
			}
		} else {
			lst=Find(x)==Find(y);
			putchar(lst+48);
		}
	} else {
		int mid=(l+r)>>1;
		Solve(p<<1,l,mid),Solve(p<<1|1,mid+1,r);
	}
	while(top>tmp) Back();
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) F[i]=i,S[i]=1;
	rep(i,1,m) {
		opt[i]=rd(),A[i]=rd(),B[i]=rd();
		if(opt[i]==1) rep(lst,0,1) {
			int x=(A[i]+lst-1)%n+1;
			int y=(B[i]+lst-1)%n+1;
			if(x>y) swap(x,y);
			if(!I[x][y]) I[x][y]=++c;
			T[I[x][y]].pb(i);
		}
	}
	rep(i,1,c) T[i].pb(m+1);
	Solve(1,1,m);
}