Forced Online Queries Problem (Codeforces 1217F)
Tags: Others, divide and conquer

You are given an undirected graph with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Initially there are no edges.You are asked to perform some queries on the graph. Let $$$last$$$ be the answer to the latest query of the second type, it is set to $$$0$$$ before the first such query. Then the queries are the following:  $$$1~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — add an undirected edge between the vertices $$$(x + last - 1)~mod~n + 1$$$ and $$$(y + last - 1)~mod~n + 1$$$ if it doesn't exist yet, otherwise remove it;  $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — check if there exists a path between the vertices $$$(x + last - 1)~mod~n + 1$$$ and $$$(y + last - 1)~mod~n + 1$$$, which goes only through currently existing edges, and set $$$last$$$ to $$$1$$$ if so and $$$0$$$ otherwise. Good luck!

Input: The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and the number of queries, respectively.Each of the following $$$m$$$ lines contains a query of one of two aforementioned types. It is guaranteed that there is at least one query of the second type.

Output: Print a string, consisting of characters '0' and '1'. The $$$i$$$-th character should be the answer to the $$$i$$$-th query of the second type. Therefore the length of the string should be equal to the number of queries of the second type.

Note: The converted queries in the first example are:  1 1 2  1 1 3  2 3 2  1 3 5  2 4 5  1 2 4  2 3 4  1 2 4  2 5 4 The converted queries in the second example are:  1 1 2  1 2 3  1 3 1  2 1 3  1 1 3  2 3 1  1 2 3  2 2 3  2 1 2 

Sample Inputs:
5 9
1 1 2
1 1 3
2 3 2
1 2 4
2 3 4
1 2 4
2 3 4
1 1 3
2 4 3

3 9
1 1 2
1 2 3
1 3 1
2 1 3
1 3 2
2 2 3
1 1 2
2 1 2
2 1 2

Sample Outputs:
1010

1101

Solution (Python):
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def bfs(s, g, c):
    (q, k) = ([s], 0)
    color[s] = c
    while len(q) ^ k:
        i = q[k]
        for j in G[i]:
            if j == g:
                return True
            if color[j] ^ c:
                q.append(j)
                color[j] = c
        k += 1
    return False
(n, m) = map(int, input().split())
txy = [tuple(map(int, input().split())) for _ in range(m)]
l = 12345
e = set()
G = [set() for _ in range(n + 1)]
color = [-1] * (n + 1)
last = 0
ans = []
for i in range(m // l + min(m % l, 1)):
    e1 = set()
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        if t == 2:
            continue
        (x1, y1) = ((x - 1) % n + 1, (y - 1) % n + 1)
        (x2, y2) = (x % n + 1, y % n + 1)
        if x1 > y1:
            (x1, y1) = (y1, x1)
        if x2 > y2:
            (x2, y2) = (y2, x2)
        if (x1, y1) in e:
            e.remove((x1, y1))
            e1.add((x1, y1))
        if (x2, y2) in e:
            e.remove((x2, y2))
            e1.add((x2, y2))
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    for (u, v) in e:
        unite(u, v)
    cnt = defaultdict(lambda : 0)
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        cnt[u, v] += 1
        if cnt[u, v] == 1:
            G[u].add(v)
            G[v].add(u)
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        (x, y) = ((x + last - 1) % n + 1, (y + last - 1) % n + 1)
        if x > y:
            (x, y) = (y, x)
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        if t == 1:
            if not (x, y) in e1:
                e1.add((x, y))
                if u ^ v:
                    cnt[u, v] += 1
                    if cnt[u, v] == 1:
                        G[u].add(v)
                        G[v].add(u)
            else:
                e1.remove((x, y))
                if u ^ v:
                    cnt[u, v] -= 1
                    if not cnt[u, v]:
                        G[u].remove(v)
                        G[v].remove(u)
        else:
            ans0 = 1 if u == v or bfs(u, v, j) else 0
            ans.append(ans0)
            last = ans0
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        e.add((x, y))
        G[u].clear()
        G[v].clear()
sys.stdout.write(''.join(map(str, ans)))

Solution (Python):
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def bfs(s, g, c):
    (q, k) = ([s], 0)
    color[s] = c
    while len(q) ^ k:
        i = q[k]
        for j in G[i]:
            if j == g:
                return True
            if color[j] ^ c:
                q.append(j)
                color[j] = c
        k += 1
    return False
(n, m) = map(int, input().split())
txy = [tuple(map(int, input().split())) for _ in range(m)]
l = 12345
e = set()
G = [set() for _ in range(n + 1)]
color = [-1] * (n + 1)
last = 0
ans = []
for i in range(m // l + min(m % l, 1)):
    e1 = set()
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        if t == 2:
            continue
        (x1, y1) = ((x - 1) % n + 1, (y - 1) % n + 1)
        (x2, y2) = (x % n + 1, y % n + 1)
        if x1 > y1:
            (x1, y1) = (y1, x1)
        if x2 > y2:
            (x2, y2) = (y2, x2)
        if (x1, y1) in e:
            e.remove((x1, y1))
            e1.add((x1, y1))
        if (x2, y2) in e:
            e.remove((x2, y2))
            e1.add((x2, y2))
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    for (u, v) in e:
        unite(u, v)
    cnt = defaultdict(lambda : 0)
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        cnt[u, v] += 1
        if cnt[u, v] == 1:
            G[u].add(v)
            G[v].add(u)
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        (x, y) = ((x + last - 1) % n + 1, (y + last - 1) % n + 1)
        if x > y:
            (x, y) = (y, x)
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        if t == 1:
            if not (x, y) in e1:
                e1.add((x, y))
                if u ^ v:
                    cnt[u, v] += 1
                    if cnt[u, v] == 1:
                        G[u].add(v)
                        G[v].add(u)
            else:
                e1.remove((x, y))
                if u ^ v:
                    cnt[u, v] -= 1
                    if not cnt[u, v]:
                        G[u].remove(v)
                        G[v].remove(u)
        else:
            ans0 = 1 if u == v or bfs(u, v, j) else 0
            ans.append(ans0)
            last = ans0
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        e.add((x, y))
        G[u].clear()
        G[v].clear()
sys.stdout.write(''.join(map(str, ans)))

Solution (Python):
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def bfs(s, g, c):
    (q, k) = ([s], 0)
    color[s] = c
    while len(q) ^ k:
        i = q[k]
        for j in G[i]:
            if j == g:
                return True
            if color[j] ^ c:
                q.append(j)
                color[j] = c
        k += 1
    return False
(n, m) = map(int, input().split())
txy = [tuple(map(int, input().split())) for _ in range(m)]
l = 12345
e = set()
G = [set() for _ in range(n + 1)]
color = [-1] * (n + 1)
last = 0
ans = []
for i in range(m // l + min(m % l, 1)):
    e1 = set()
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        if t == 2:
            continue
        (x1, y1) = ((x - 1) % n + 1, (y - 1) % n + 1)
        (x2, y2) = (x % n + 1, y % n + 1)
        if x1 > y1:
            (x1, y1) = (y1, x1)
        if x2 > y2:
            (x2, y2) = (y2, x2)
        if (x1, y1) in e:
            e.remove((x1, y1))
            e1.add((x1, y1))
        if (x2, y2) in e:
            e.remove((x2, y2))
            e1.add((x2, y2))
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    for (u, v) in e:
        unite(u, v)
    cnt = defaultdict(lambda : 0)
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        cnt[u, v] += 1
        if cnt[u, v] == 1:
            G[u].add(v)
            G[v].add(u)
    for j in range(i * l, min((i + 1) * l, m)):
        (t, x, y) = txy[j]
        (x, y) = ((x + last - 1) % n + 1, (y + last - 1) % n + 1)
        if x > y:
            (x, y) = (y, x)
        (u, v) = (get_root(x), get_root(y))
        if u > v:
            (u, v) = (v, u)
        if t == 1:
            if not (x, y) in e1:
                e1.add((x, y))
                if u ^ v:
                    cnt[u, v] += 1
                    if cnt[u, v] == 1:
                        G[u].add(v)
                        G[v].add(u)
            else:
                e1.remove((x, y))
                if u ^ v:
                    cnt[u, v] -= 1
                    if not cnt[u, v]:
                        G[u].remove(v)
                        G[v].remove(u)
        else:
            ans0 = 1 if u == v or bfs(u, v, j) else 0
            ans.append(ans0)
            last = ans0
    for (x, y) in e1:
        (u, v) = (get_root(x), get_root(y))
        e.add((x, y))
        G[u].clear()
        G[v].clear()
sys.stdout.write(''.join(map(str, ans)))