题目连接 题意： 给你一个n点m边无向图。有q次查询，每次查询区间l， r。问：该区间中的边形成的子图能否构成至少一个简单环。查询必须在线。 题解： 对于每个边i，我们都可以找出从它开始最早的可以形成简单环的端点，即区间[ i, ans[i] ]，这里有结论，f(i)=ans[i]是单调递增的。所以可以尺取。对于所有i，求出最短区间，然后就可以O（1）查了。 这里需要一个数据结构：可以动态断边、删边、并查看该图任意两点的联通性（又不需要真正的连接环，这点很重要）。显然是LCT了。在判定两点是否联通时，我们先将一个点拉为原树根，然后判另一个节点的根是否为它。(当然可以判定findroot(x)==findroot(y)，但理论上在随机数据下的期望应该会比较慢，实测慢了200+ms) 下面是ac代码：
#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); using namespace std; const int maxn = 3e5+5; struct Node { int fa,ch[2],val,res; //res是异或结果 bool tag; //翻转懒标记 }spl[maxn]; #define ls(x) (spl[x].ch[0]) #define rs(x) (spl[x].ch[1]) #define fa(x) (spl[x].fa) #define ident(x,f) (rs(f)==x) #define connect(x,f,s) spl[fa(x)=f].ch[s]=x //-------------update------------------------------------ #define update(x) spl[x].res=spl[ls(x)].res^spl[rs(x)].res^spl[x].val //-------------update------------------------------------ #define ntroot(x) (ls(fa(x))==x||rs(fa(x))==x) //判断结点是否为Splay的根 #define reverse(x) std::swap(ls(x),rs(x)),spl[x].tag^=1 inline void pushdw(int x) //懒标记下传 { if(spl[x].tag) { if(ls(x)) reverse(ls(x)); if(rs(x)) reverse(rs(x)); } spl[x].tag=0; } void pushall(int x) //头递归，从上到下下传所有懒标记 { if(ntroot(x)) pushall(fa(x)); pushdw(x); } inline void rotate(int x) //Splay基操 { int f=fa(x),ff=fa(f),k=ident(x,f); connect(spl[x].ch[k^1],f,k); fa(x)=ff; if(ntroot(f)) spl[ff].ch[ident(f,ff)]=x;//※重要，不能忘记判断，关系到虚实边 connect(f,x,k^1); update(f),update(x); } inline void splaying(int x) //Splay基操，都是伸展到根结点 { pushall(x); //要先把上面的懒标记全都下传 while(ntroot(x)) { int f=fa(x),ff=fa(f); if(ntroot(f)) ident(f,ff)^ident(x,f)?rotate(x):rotate(f); rotate(x); } } inline void access(int x) //从x到原树根结点拉一条实链 { for(int y=0;x;x=fa(y=x)) //y为上一个Splay的根 { splaying(x); //伸展到当前Splay的根 rs(x)=y; //右儿子连上上一个Splay的根 update(x); //别忘更新＞﹏＜ } } inline void mkroot(int x) //给原树换根 { access(x); //先拉实链，拉好后x一定在Splay的最右（深度最大） splaying(x); //再伸展，伸展后x必定没有右儿子 reverse(x); //翻转拉出来这条实链，使深度顺序翻转 } inline int findroot(int x) //寻找结点在原树的根 { access(x); //先拉实链 splaying(x); //再伸展 while(ls(x)) //因为根结点必定深度最小，所以不停往左找就OK了 { pushdw(x); //别忘了下传，第一个儿子是没问题的但是第二个往后…… x=ls(x); } splaying(x); //用来保证时间复杂度，防止卡链 return x; } inline void link(int x,int y) //连边，不保证数据合法 { mkroot(x); //换根 if(findroot(y)==x) return; //如果y所在的树的根结点是x，那说明两者在一棵树上 fa(x)=y; } inline void cut(int x,int y) //断边，不保证数据合法 { mkroot(x); //换根 if(findroot(y)!=x||fa(y)!=x||ls(y)) return; fa(y)=rs(x)=0; //双向断边 update(x); } inline void split(int x,int y) //把x--y的路径拆出来 { mkroot(x); //换根 access(y); //拉实链 splaying(y); //伸展 //? 此时y必定没有右儿子且左儿子是一条到x的实链，所以访问y就可以作任何关于这条链的操作了 } bool isConnect(int x, int y) { mkroot(x); return findroot(y) == x; } struct Ed { int v, u; }e[maxn]; int ans[maxn]; int main() { int t; scanf("%d", &t); while(t--) { int n, m, q; scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= m; i++) scanf("%d%d", &e[i].u, &e[i].v); int r = 1; for (int i = 1; i <= m; i++) { while(r <= m && !isConnect(e[r].u, e[r].v)) { link(e[r].u, e[r].v); r++; } ans[i] = r; cut(e[i].v, e[i].u); } int la = 0; while(q--) { int l, r; scanf("%d%d", &l, &r); l = (l ^ la) % m + 1; r = (r ^ la) % m + 1; if (l > r) swap(l, r); if (ans[l] <= r) puts("Yes"), la = 1; else puts("No"), la = 0; } } return 0; }