Educational Codeforces Round 72 F. Forced Online Queries Problem
题目梗概
有一张\(n\)个点的图，刚开始没有边,现在又两种操作，一种是加入一条边（如果这条边存在，否则删去这条边），一种是询问\(x,y\)是否联通。
\(x,y\)给出的形式是\((x+last-1)%n+1\),\((y+last-1)%n+1\),\(last\)为上一次询问的答案。
解题思路
对于这题的离线版本有两种写法：线段树分治，以及对操作分块。
线段树分治的做法比较常见，下面来讲讲分块的做法。
对于当前块之前的操作，我们可以找出哪些边在当前块需要操作，设为集合\(B\)，当然就有不需要操作的边，设为集合\(C\)。
对于集合\(C\)我们可以提前建好边，然后对于当前块的操作：如果是修改，那么直接修改集合\(B\)；如果是询问，就往集合\(C\)暴力加入集合\(B\)的边，然后查询。
因为集合\(C\)的构建次数不超过\(m/P\)，集合\(B\)的大小不超过\(P\)，所以复杂度为\(m\sqrt mlogm\)。
那么回到这道题，分块的做法十分的显然，集合\(B\)的定义改成可能操作的边的集合即可。
其实线段树分治也是可以的，因为分治的过程也是按时间顺序，我们考虑这条边可能加入的位置。
如果这条边是第奇数次确定加入，那么就可以贡献到下次可能出现的位置，直到某个位置也确定加入（即删除）。
#include
#include
#include
#include
#define pr pair
#define mk make_pair
#define fr first
#define sc second
#define IT set::iterator
using namespace std;
const int maxn=400005;
inline int _read(){int num=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar();return num;
}
struct jz{int x,y;jz(int x=0,int y=0):x(x),y(y){}
}S[maxn];
set A,B,C;
void add(set &S,pr x){if (S.find(x)==S.end()) S.insert(x);else S.erase(x);}
int n,m,L,R,K,ans[maxn],tg[maxn],tim,top,s[maxn],f[maxn];
pr ed[maxn][2];
int get(int x){if (f[x]==x) return x;return get(f[x]);}
void merge(int x,int y){x=get(x);y=get(y);if (x==y) return;if (s[x]y) swap(x,y);ed[i][0]=mk(x,y);x=x%n+1;y=y%n+1;if (x>y) swap(x,y);ed[i][1]=mk(x,y);if (tg[i]==1) A.insert(ed[i][0]),A.insert(ed[i][1]);}for (int i=1;i 转载于:https://www.cnblogs.com/CHNJZ/p/11508728.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！