nn个点，mm次操作：

  • 1, _x, _y

    令x=(_x+last−1)mod n+1,y=(_y+last−1)mod n+1x = (\_x + last - 1) \mathrm{mod}~n + 1, y=(\_y + last - 1) \mathrm{mod}~n + 1

    若(x,y)(x, y)已经连接，则删掉(x,y)(x, y)，否则连接(x,y)(x, y)

  • 2, _x, _y

    令x=(_x+last−1)mod n+1,y=(_y+last−1)mod n+1x = (\_x + last - 1) \mathrm{mod}~n + 1, y=(\_y + last - 1) \mathrm{mod}~n + 1

    询问xx和yy是否联通，输出0/10/1

其中lastlast表示上一次询问的答案

n,m≤2×105n, m\le 2\times 10^5

CF1217 F

Solution

看上去是一道动态图板子

但实际上因为这里的答案只可能是0/10/1，可能的操作只有两种，所以可以离线线段树分治搞

具体来说，对于一次修改，把两种可能的操作都先搞出来。对于一个操作(x,y)(x, y)，处理出它后面第一个可能的操作时间nxtnxt

线段树分治时，维护一个全局的Sx,yS_{x, y}，表示边(x,y)(x, y)当前的状态（已经连上/没连上）

线段树处理到l ==r的时候，我们是知道当前的答案的，于是把答案对应的那一种操作的SS异或上11。再对两种操作看其SS是否为11，若为11，则在分治的线段树中，把当前操作应用到[l+1,nxt][l + 1, nxt]区间上

感觉没讲清楚。。。不过脑补一下并不难

Summary

这个离线做法本质上是把所有可能的情况都处理出来，把操作拆成若干段，只有跨过段的时候这条边的影响才有可能变化

感觉是很巧妙的一道题

Code

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;

int N, M;
map <pii, int> Map, S;
struct opt
{
	int op, x, y, ban;
	int l[2], r[2];
} Q[Maxn];

int ans;

inline int trans (int x, int k) { return (x + k - 1) % N + 1; }

namespace DSU
{
	int fa[Maxn], size[Maxn], top;

	struct edge
	{
		int x, y, f;
	} stk[Maxn];

	inline void init () { for (int i = 1; i <= N; ++i) fa[i] = i, size[i] = 1; }

	inline int get_fa (int x) { return fa[x] == x ? x : get_fa (fa[x]); }

	inline void link (int x, int y)
	{
		x = get_fa (x), y = get_fa (y);
		if (size[x] < size[y]) swap (x, y);

		stk[++top] = (edge) {x, y, fa[y]};
		if (x != y) fa[y] = x, size[x] += size[y];
	}

	inline void pop ()
	{
		int x = stk[top].x, y = stk[top].y, f = stk[top].f; --top;
		size[x] -= size[y];
		fa[y] = f;
	}

	inline int query (int x, int y) { return get_fa (x) == get_fa (y); }
}

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1 
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r

	vector <pii> node[Maxn << 2];

	inline void update (int o, int l, int r, int x, int y, pii val)
	{
		if (x > y) return ;
		if (x <= l && r <= y) return void (node[o].pb (val));
		if (x <= mid) update (lson, x, y, val);
		if (y > mid) update (rson, x, y, val);
	}

	inline void solve (int o, int l, int r)
	{
		for (int i = 0; i < node[o].size(); ++i) DSU :: link (node[o][i].x, node[o][i].y);

		if (l == r)
		{
			if (Q[l].op == 2) printf("%d", ans = DSU :: query (trans (Q[l].x, ans), trans (Q[l].y, ans)));
			else
			{
				for (int k = 0; k < 2; ++k)
				{
					if (Q[l].ban && ans != k) continue;
					int x = trans (Q[l].x, k), y = trans (Q[l].y, k);
					if (x > y) swap (x, y);
					if (ans == k) S[mp (x, y)] ^= 1;
					if (S[mp (x, y)]) SEG :: update (1, 1, M, Q[l].l[k], Q[l].r[k], mp (x, y));
				}
			}
		}
		else solve (lson), solve (rson);

		for (int i = 0; i < node[o].size(); ++i) DSU :: pop ();
	}
#undef mid
}

inline void Solve ()
{
	for (int i = M; i >= 1; --i)
	{
		if (Q[i].op == 2) continue;
		for (int k = 0; k < 2; ++k)
		{
			int x = trans (Q[i].x, k), y = trans (Q[i].y, k);
			if (x > y) swap (x, y);

			Q[i].l[k] = i + 1, Q[i].r[k] = M;
			if (Map[mp (x, y)])
			{
				if (Map[mp (x, y)] == i) Q[i].ban = 1, Q[i].r[k] = Q[i].r[!k];
				else Q[i].r[k] = Map[mp (x, y)];
			}
			Map[mp (x, y)] = i;
		}
	}

	DSU :: init ();
	SEG :: solve (1, 1, M);
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= M; ++i)
		Q[i].op = read<int>(), Q[i].x = read<int>(), Q[i].y = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}