HDU-6858 Discovery of Cycles （LCT,双指针,ST表）
Problem Description
In response to the 8202 Olympics, Quber City, which was the host of the competition, is planning to build a magnificent stadium. The stadium is nowhere close to traditional stadiums that are typically embedded with a cyclic running trail. According to the plan, there are n service spots in the stadium, and m undirected running trails connecting them. Such adventurous design has brought worldwide attention to the stadium, but also comes with a huge cost.
Therefore the designers are working to simplify the design to cut down the cost. They discovered that the easiest way to do this is to sort the m running trails in some particular order, and keep only some consecutive trails in the list. Since only part of the trails will be built, fund will be saved and everyone will be happy --- perhaps except those long-distance runners who needs a cyclic trail for the competition. A cyclic trail is a trail that starts at some service spot, passes through some distinct spots, before getting back to where it starts. All the running trails that have been used are required to be distinct. (This is by definition a simple cycle if you are familiar with terms in graph theory.)
Your task is to write a program that can quickly check, whether one can find at least one simple cycle, given that the stadium is built with some particular running trails selected consecutively from the trail list.
思路：
双指针维护出(R_i)代表以第(mathit i) 个边开始加边，第一个会产生环的位置。
需要用LCT的加边，删边，查询连通性这三个功能。
然后对于(mathit R) 数组简历(ST) 表，那么对于每一个询问，我们只需要用(ST)表询问([l,r])区间最小值，然后将其与(mathit r) 比较下大小关系即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), ' ', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) if(DEBUG_Switch) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
ll poww(ll a, ll b) { if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a ;} a = a * a ; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("
");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("
");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
void pvarr_int(int *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%d%c", arr[i], i == n ? '
' : ' ');}}
void pvarr_LL(ll *arr, int n, int strat = 1) {if (strat == 0) {n--;} repd(i, strat, n) {printf("%lld%c", arr[i], i == n ? '
' : ' ');}}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
const int N = 300000 + 10;
struct node {
int ch[2], p;
int revFlag;
} nod[N];
void revInterval(int x) {
nod[x].revFlag ^= 1;
swap(nod[x].ch[0], nod[x].ch[1]);
}
void pushdown(int x) {
if (nod[x].revFlag) {
if (nod[x].ch[0]) revInterval(nod[x].ch[0]);
if (nod[x].ch[1]) revInterval(nod[x].ch[1]);
nod[x].revFlag = 0;
}
}
int type(int x) {
if (nod[nod[x].p].ch[0] == x) return 0;
if (nod[nod[x].p].ch[1] == x) return 1;
return -1;
}
void rotate(int x) {
int y = nod[x].p, z = nod[y].p, typo = type(x);
if (type(y) != -1) {
nod[z].ch[type(y)] = x;
}
nod[x].p = z;
nod[y].ch[typo] = nod[x].ch[typo ^ 1], nod[nod[x].ch[typo ^ 1]].p = y;
nod[x].ch[typo ^ 1] = y; nod[y].p = x;
}
void down(int x) {
if (type(x) != -1) down(nod[x].p);
pushdown(x);
}
void splay(int x) {
down(x);
for (; type(x) != -1 ; rotate(x)) {
if (type(nod[x].p) != -1) {
if (type(nod[x].p) == type(x))
rotate(nod[x].p);
else
rotate(x);
}
}
}
void access(int x) {
int y = 0;
while (x) {
splay(x);
nod[x].ch[1] = y;
y = x, x = nod[x].p;
}
}
void makeroot(int x) {
access(x);
splay(x);
revInterval(x);
}
int findroot(int x) {
access(x);
splay(x);
while (nod[x].ch[0]) pushdown(x), x = nod[x].ch[0];
return x;
}
void link(int x, int y) {
makeroot(x); nod[x].p = y;
}
void split(int x, int y) {
makeroot(x);
access(y);
splay(y);
}
void cut(int x, int y) {
makeroot(x);
if (findroot(y) != x || nod[x].p != y || nod[x].ch[1]) return ;
nod[x].p = nod[y].ch[0] = 0;
}
void init(int n)
{
repd(i, 1, n)
{
nod[i].p = 0;
nod[i].ch[0] = nod[i].ch[1] = 0;
}
}
int n, q, op, x, y, m;
pii e[maxn];
int r[maxn];
int st1[maxn][25];//st表
int st2[maxn][25];//st表
void init_st(int n)
{
for (int i = 0; i < n; i++)
{
st2[i][0] = r[i + 1];
}
for (int i = 1; (1 << i) <= n; i++)
{
for (int j = 0; j + (1 << i) - 1 < n; j++)
{
st2[j][i] = min(st2[j][i - 1], st2[j + (1 << (i - 1))][i - 1]);
}
}
}
inline int queryemin(int l, int r)
{
l--;
r--;
int k = (int)(log((double)(r - l + 1)) / log(2.0));
return min(st2[l][k], st2[r - (1 << k) + 1][k]);
}
int main()
{
int t;
t = readint();
while (t--)
{
n = readint(); m = readint(); q = readint();
repd(i, 1, m)
{
e[i].fi = readint();
e[i].se = readint();
}
int id = 1;
repd(i, 1, m)
{
r[i] = m + 1;
while (id <= m)
{
x = e[id].fi; y = e[id].se;
if (findroot(x) == findroot(y))
{
r[i] = id;
break;
} else {
link(x, y);
id++;
}
}
x = e[i].fi; y = e[i].se;
cut(x, y);
}
init_st(m);
int lastans = 0;
while (q--)
{
int l = readint(); int r = readint();
int k1 = (l ^ lastans) % m + 1;
int k2 = (r ^ lastans) % m + 1;
l = min(k1, k2);
r = max(k1, k2);
int res = queryemin(l, r);
if (res <= r)
{
lastans = 1;
printf("Yes
");
} else
{
lastans = 0;
printf("No
");
}
}
init(n);
}
return 0;
}