Graph and Queries (Codeforces 1416D)
Tags: Implement, dsu

You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Initially there is a single integer written on every vertex: the vertex $$$i$$$ has $$$p_i$$$ written on it. All $$$p_i$$$ are distinct integers from $$$1$$$ to $$$n$$$.You have to process $$$q$$$ queries of two types:  $$$1$$$ $$$v$$$ — among all vertices reachable from the vertex $$$v$$$ using the edges of the graph (including the vertex $$$v$$$ itself), find a vertex $$$u$$$ with the largest number $$$p_u$$$ written on it, print $$$p_u$$$ and replace $$$p_u$$$ with $$$0$$$;  $$$2$$$ $$$i$$$ — delete the $$$i$$$-th edge from the graph.  Note that, in a query of the first type, it is possible that all vertices reachable from $$$v$$$ have $$$0$$$ written on them. In this case, $$$u$$$ is not explicitly defined, but since the selection of $$$u$$$ does not affect anything, you can choose any vertex reachable from $$$v$$$ and print its value (which is $$$0$$$). 

Input: The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 3 \cdot 10^5$$$; $$$1 \le q \le 5 \cdot 10^5$$$).The second line contains $$$n$$$ distinct integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$, where $$$p_i$$$ is the number initially written on vertex $$$i$$$ ($$$1 \le p_i \le n$$$).Then $$$m$$$ lines follow, the $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) and means that the $$$i$$$-th edge connects vertices $$$a_i$$$ and $$$b_i$$$. It is guaranteed that the graph does not contain multi-edges.Then $$$q$$$ lines follow, which describe the queries. Each line is given by one of the following formats:  $$$1$$$ $$$v$$$ — denotes a query of the first type with a vertex $$$v$$$ ($$$1 \le v \le n$$$).  $$$2$$$ $$$i$$$ — denotes a query of the second type with an edge $$$i$$$ ($$$1 \le i \le m$$$). For each query of the second type, it is guaranteed that the corresponding edge is not deleted from the graph yet. 

Output: For every query of the first type, print the value of $$$p_u$$$ written on the chosen vertex $$$u$$$.


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

Sample Outputs:
5
1
2
0

Solution (Python):
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):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    if rank[s] == rank[t]:
        rank[s] += 1
    root[t] = s
    size[s] += size[t]
    (ls, rt) = (l[s], r[t])
    (l[s], r[t]) = (l[t], r[s])
    return (ls, rt)

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

def get_size(s):
    return size[get_root(s)]

def f(u, v):
    return u * n + v

def update(i, x):
    i += l1
    tree[i] = x
    i >>= 1
    while i:
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i >>= 1
    return

def get_max(s, t):
    (s, t) = (s + l1, t + l1)
    ans = 0
    while s <= t:
        if s & 1:
            ans = max(ans, tree[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree[t])
            t -= 1
        t >>= 1
    return ans
(n, m, q) = map(int, input().split())
p = [0] + list(map(int, input().split()))
(a, b) = ([0] * (m + 1), [0] * (m + 1))
for i in range(1, m + 1):
    (a0, b0) = map(int, input().split())
    (a[i], b[i]) = (a0, b0)
(t, z) = ([0] * q, [0] * q)
e = [1] * (m + 1)
for i in range(q):
    (t0, z0) = map(int, input().split())
    if t0 == 2:
        e[z0] = 0
    (t[i], z[i]) = (t0, z0)
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
l = [i for i in range(n + 1)]
r = [i for i in range(n + 1)]
cnt = [0] * (n + 1)
nx = [0] * (n + 1)
for i in range(1, m + 1):
    (x, y) = (a[i], b[i])
    if e[i] and (not same(x, y)):
        (u, v) = unite(x, y)
        nx[u] ^= v
        nx[v] ^= u
(ll, rr) = ([0] * q, [0] * q)
for i in range(q - 1, -1, -1):
    j = z[i]
    if t[i] == 1:
        (ll[i], rr[i]) = (l[get_root(j)], r[get_root(j)])
    else:
        (x, y) = (a[j], b[j])
        if not same(x, y):
            (u, v) = unite(x, y)
            nx[u] ^= v
            nx[v] ^= u
(i, k) = (l[get_root(1)], 1)
(p0, q0) = ([0] * (n + 1), [-1] * (n + 1))
(p0[0], q0[i]) = (p[i], 0)
for j in range(1, n):
    if not nx[i]:
        while q0[k] ^ -1:
            k += 1
        i = l[get_root(k)]
    else:
        nx[nx[i]] ^= i
        i = nx[i]
    (p0[j], q0[i]) = (p[i], j)
l1 = pow(2, (n + 1).bit_length())
l2 = 2 * l1
tree = [0] * l2
for i in range(n):
    tree[i + l1] = f(p0[i], i)
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
ans = []
for i in range(q):
    if t[i] == 2:
        continue
    (x, y) = (q0[ll[i]], q0[rr[i]])
    if x > y:
        (x, y) = (y, x)
    (ans0, j) = divmod(get_max(x, y), n)
    ans.append(ans0)
    if ans0:
        update(j, 0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
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):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    if rank[s] == rank[t]:
        rank[s] += 1
    root[t] = s
    size[s] += size[t]
    (ls, rt) = (l[s], r[t])
    (l[s], r[t]) = (l[t], r[s])
    return (ls, rt)

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

def get_size(s):
    return size[get_root(s)]

def f(u, v):
    return u * n + v

def update(i, x):
    i += l1
    tree[i] = x
    i >>= 1
    while i:
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i >>= 1
    return

def get_max(s, t):
    (s, t) = (s + l1, t + l1)
    ans = 0
    while s <= t:
        if s & 1:
            ans = max(ans, tree[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree[t])
            t -= 1
        t >>= 1
    return ans
(n, m, q) = map(int, input().split())
p = [0] + list(map(int, input().split()))
(a, b) = ([0] * (m + 1), [0] * (m + 1))
for i in range(1, m + 1):
    (a0, b0) = map(int, input().split())
    (a[i], b[i]) = (a0, b0)
(t, z) = ([0] * q, [0] * q)
e = [1] * (m + 1)
for i in range(q):
    (t0, z0) = map(int, input().split())
    if t0 == 2:
        e[z0] = 0
    (t[i], z[i]) = (t0, z0)
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
l = [i for i in range(n + 1)]
r = [i for i in range(n + 1)]
cnt = [0] * (n + 1)
nx = [0] * (n + 1)
for i in range(1, m + 1):
    (x, y) = (a[i], b[i])
    if e[i] and (not same(x, y)):
        (u, v) = unite(x, y)
        nx[u] ^= v
        nx[v] ^= u
(ll, rr) = ([0] * q, [0] * q)
for i in range(q - 1, -1, -1):
    j = z[i]
    if t[i] == 1:
        (ll[i], rr[i]) = (l[get_root(j)], r[get_root(j)])
    else:
        (x, y) = (a[j], b[j])
        if not same(x, y):
            (u, v) = unite(x, y)
            nx[u] ^= v
            nx[v] ^= u
(i, k) = (l[get_root(1)], 1)
(p0, q0) = ([0] * (n + 1), [-1] * (n + 1))
(p0[0], q0[i]) = (p[i], 0)
for j in range(1, n):
    if not nx[i]:
        while q0[k] ^ -1:
            k += 1
        i = l[get_root(k)]
    else:
        nx[nx[i]] ^= i
        i = nx[i]
    (p0[j], q0[i]) = (p[i], j)
l1 = pow(2, (n + 1).bit_length())
l2 = 2 * l1
tree = [0] * l2
for i in range(n):
    tree[i + l1] = f(p0[i], i)
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
ans = []
for i in range(q):
    if t[i] == 2:
        continue
    (x, y) = (q0[ll[i]], q0[rr[i]])
    if x > y:
        (x, y) = (y, x)
    (ans0, j) = divmod(get_max(x, y), n)
    ans.append(ans0)
    if ans0:
        update(j, 0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
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):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    if rank[s] == rank[t]:
        rank[s] += 1
    root[t] = s
    size[s] += size[t]
    (ls, rt) = (l[s], r[t])
    (l[s], r[t]) = (l[t], r[s])
    return (ls, rt)

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

def get_size(s):
    return size[get_root(s)]

def f(u, v):
    return u * n + v

def update(i, x):
    i += l1
    tree[i] = x
    i >>= 1
    while i:
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i >>= 1
    return

def get_max(s, t):
    (s, t) = (s + l1, t + l1)
    ans = 0
    while s <= t:
        if s & 1:
            ans = max(ans, tree[s])
            s += 1
        s >>= 1
        if not t & 1:
            ans = max(ans, tree[t])
            t -= 1
        t >>= 1
    return ans
(n, m, q) = map(int, input().split())
p = [0] + list(map(int, input().split()))
(a, b) = ([0] * (m + 1), [0] * (m + 1))
for i in range(1, m + 1):
    (a0, b0) = map(int, input().split())
    (a[i], b[i]) = (a0, b0)
(t, z) = ([0] * q, [0] * q)
e = [1] * (m + 1)
for i in range(q):
    (t0, z0) = map(int, input().split())
    if t0 == 2:
        e[z0] = 0
    (t[i], z[i]) = (t0, z0)
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
size = [1 for _ in range(n + 1)]
l = [i for i in range(n + 1)]
r = [i for i in range(n + 1)]
cnt = [0] * (n + 1)
nx = [0] * (n + 1)
for i in range(1, m + 1):
    (x, y) = (a[i], b[i])
    if e[i] and (not same(x, y)):
        (u, v) = unite(x, y)
        nx[u] ^= v
        nx[v] ^= u
(ll, rr) = ([0] * q, [0] * q)
for i in range(q - 1, -1, -1):
    j = z[i]
    if t[i] == 1:
        (ll[i], rr[i]) = (l[get_root(j)], r[get_root(j)])
    else:
        (x, y) = (a[j], b[j])
        if not same(x, y):
            (u, v) = unite(x, y)
            nx[u] ^= v
            nx[v] ^= u
(i, k) = (l[get_root(1)], 1)
(p0, q0) = ([0] * (n + 1), [-1] * (n + 1))
(p0[0], q0[i]) = (p[i], 0)
for j in range(1, n):
    if not nx[i]:
        while q0[k] ^ -1:
            k += 1
        i = l[get_root(k)]
    else:
        nx[nx[i]] ^= i
        i = nx[i]
    (p0[j], q0[i]) = (p[i], j)
l1 = pow(2, (n + 1).bit_length())
l2 = 2 * l1
tree = [0] * l2
for i in range(n):
    tree[i + l1] = f(p0[i], i)
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
ans = []
for i in range(q):
    if t[i] == 2:
        continue
    (x, y) = (q0[ll[i]], q0[rr[i]])
    if x > y:
        (x, y) = (y, x)
    (ans0, j) = divmod(get_max(x, y), n)
    ans.append(ans0)
    if ans0:
        update(j, 0)
sys.stdout.write('\n'.join(map(str, ans)))