Communication Towers (Codeforces 1814F)
Tags: Others, divide and conquer

There are $$$n$$$ communication towers, numbered from $$$1$$$ to $$$n$$$, and $$$m$$$ bidirectional wires between them. Each tower has a certain set of frequencies that it accepts, the $$$i$$$-th of them accepts frequencies from $$$l_i$$$ to $$$r_i$$$.Let's say that a tower $$$b$$$ is accessible from a tower $$$a$$$, if there exists a frequency $$$x$$$ and a sequence of towers $$$a=v_1, v_2, \dots, v_k=b$$$, where consecutive towers in the sequence are directly connected by a wire, and each of them accepts frequency $$$x$$$. Note that accessibility is not transitive, i. e if $$$b$$$ is accessible from $$$a$$$ and $$$c$$$ is accessible from $$$b$$$, then $$$c$$$ may not be accessible from $$$a$$$.Your task is to determine the towers that are accessible from the $$$1$$$-st tower.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le 4 \cdot 10^5$$$) — the number of communication towers and the number of wires, respectively.Then $$$n$$$ lines follows, the $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) — the boundaries of the acceptable frequencies for the $$$i$$$-th tower.Then $$$m$$$ lines follows, the $$$i$$$-th of them contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$) — the $$$i$$$-th wire that connects towers $$$v_i$$$ and $$$u_i$$$. There are no two wires connecting the same pair of towers. 

Output: In a single line, print distinct integers from $$$1$$$ to $$$n$$$ in ascending order — the indices of the communication towers that are accessible from the $$$1$$$-st tower.


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

3 1
2 3
1 4
1 1
1 3

5 5
1 3
2 3
2 2
3 5
2 4
1 2
2 3
3 4
4 1
4 5

Sample Outputs:
1 3 5 6

1

1 2 3 4 5

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

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

def get_root(s):
    while s ^ root[s]:
        s = root[s]
    return s

def unite(s, t, i):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    (c1, c2, c3, c4) = (s, 0, t, root[t])
    if rank[s] == rank[t]:
        rank[s] += 1
        c2 = 1
    root[t] = s
    st1.append(f(c1, c3, c4))
    st2.append(4 * i + 2 * c2 + ok[s])
    ok[s] = min(s ^ get_root(0), 1) ^ 1
    return

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

def undo(x, y):
    (s, t0) = divmod(x, n * n)
    (t, rt) = divmod(t0, n)
    (c, oks) = divmod(y % 4, 2)
    rank[s] -= c
    root[t] = rt
    if ok[s]:
        ok[t] = 1
    else:
        ok[s] = oks
    return
(n, m) = map(int, input().split())
(l, r) = ([0] * n, [0] * n)
for i in range(n):
    (l0, r0) = map(int, input().split())
    (l[i], r[i]) = (l0, r0)
(u, v) = ([0] * m, [0] * m)
for i in range(m):
    (u0, v0) = map(int, input().split())
    (u[i], v[i]) = (u0 - 1, v0 - 1)
z = 2 * pow(10, 5) + 5
l1 = pow(2, (z + 1).bit_length())
l2 = 2 * l1
s0 = [0] * l2
for (u0, v0) in zip(u, v):
    l0 = max(l[u0], l[v0]) + l1
    r0 = min(r[u0], r[v0]) + l1
    while l0 <= r0:
        if l0 & 1:
            s0[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            s0[r0] += 1
            r0 -= 1
        r0 >>= 1
for i in range(1, l2):
    s0[i] += s0[i - 1]
now = [0] + list(s0)
tree = [-1] * now[l2]
for i in range(m):
    (u0, v0) = (u[i], v[i])
    l0 = max(l[u0], l[v0]) + l1
    r0 = min(r[u0], r[v0]) + l1
    while l0 <= r0:
        if l0 & 1:
            tree[now[l0]] = i
            now[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            tree[now[r0]] = i
            now[r0] += 1
            r0 -= 1
        r0 >>= 1
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
ok = [0] * (n + 1)
ok[0] = 1
s0 = [0] + s0
(st1, st2) = ([], [])
now = 1
for i in range(s0[1], s0[2]):
    j = tree[i]
    unite(u[j], v[j], 1)
visit = [0] * l2
while now:
    if now >= l1 or visit[now << 1 ^ 1]:
        visit[now] = 1
        while st1 and st2[-1] >> 2 == now:
            undo(st1.pop(), st2.pop())
        now >>= 1
        continue
    now = now << 1 if not visit[now << 1] else now << 1 ^ 1
    for i in range(s0[now], s0[now + 1]):
        j = tree[i]
        unite(u[j], v[j], now)
ans = []
for i in range(n):
    if ok[i]:
        ans.append(i + 1)
sys.stdout.write(' '.join(map(str, ans)))

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

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

def get_root(s):
    while s ^ root[s]:
        s = root[s]
    return s

def unite(s, t, i):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    (c1, c2, c3, c4) = (s, 0, t, root[t])
    if rank[s] == rank[t]:
        rank[s] += 1
        c2 = 1
    root[t] = s
    st1.append(f(c1, c3, c4))
    st2.append(4 * i + 2 * c2 + ok[s])
    ok[s] = min(s ^ get_root(0), 1) ^ 1
    return

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

def undo(x, y):
    (s, t0) = divmod(x, n * n)
    (t, rt) = divmod(t0, n)
    (c, oks) = divmod(y % 4, 2)
    rank[s] -= c
    root[t] = rt
    if ok[s]:
        ok[t] = 1
    else:
        ok[s] = oks
    return
(n, m) = map(int, input().split())
(l, r) = ([0] * n, [0] * n)
for i in range(n):
    (l0, r0) = map(int, input().split())
    (l[i], r[i]) = (l0, r0)
(u, v) = ([0] * m, [0] * m)
for i in range(m):
    (u0, v0) = map(int, input().split())
    (u[i], v[i]) = (u0 - 1, v0 - 1)
z = 2 * pow(10, 5) + 5
l1 = pow(2, (z + 1).bit_length())
l2 = 2 * l1
s0 = [0] * l2
for (u0, v0) in zip(u, v):
    l0 = max(l[u0], l[v0]) + l1
    r0 = min(r[u0], r[v0]) + l1
    while l0 <= r0:
        if l0 & 1:
            s0[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            s0[r0] += 1
            r0 -= 1
        r0 >>= 1
for i in range(1, l2):
    s0[i] += s0[i - 1]
now = [0] + list(s0)
tree = [-1] * now[l2]
for i in range(m):
    (u0, v0) = (u[i], v[i])
    l0 = max(l[u0], l[v0]) + l1
    r0 = min(r[u0], r[v0]) + l1
    while l0 <= r0:
        if l0 & 1:
            tree[now[l0]] = i
            now[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            tree[now[r0]] = i
            now[r0] += 1
            r0 -= 1
        r0 >>= 1
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
ok = [0] * (n + 1)
ok[0] = 1
s0 = [0] + s0
(st1, st2) = ([], [])
now = 1
for i in range(s0[1], s0[2]):
    j = tree[i]
    unite(u[j], v[j], 1)
visit = [0] * l2
while now:
    if now >= l1 or visit[now << 1 ^ 1]:
        visit[now] = 1
        while st1 and st2[-1] >> 2 == now:
            undo(st1.pop(), st2.pop())
        now >>= 1
        continue
    now = now << 1 if not visit[now << 1] else now << 1 ^ 1
    for i in range(s0[now], s0[now + 1]):
        j = tree[i]
        unite(u[j], v[j], now)
ans = []
for i in range(n):
    if ok[i]:
        ans.append(i + 1)
sys.stdout.write(' '.join(map(str, ans)))

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

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

def get_root(s):
    while s ^ root[s]:
        s = root[s]
    return s

def unite(s, t, i):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    if rank[s] < rank[t]:
        (s, t) = (t, s)
    (c1, c2, c3, c4) = (s, 0, t, root[t])
    if rank[s] == rank[t]:
        rank[s] += 1
        c2 = 1
    root[t] = s
    st.append((i, c1, c2, c3, c4, ok[s]))
    ok[s] = min(s ^ get_root(0), 1) ^ 1
    return

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

def undo(x):
    (_, s, c, t, rt, oks) = x
    rank[s] -= c
    root[t] = rt
    if ok[s]:
        ok[t] = 1
    else:
        ok[s] = oks
    return
(n, m) = map(int, input().split())
(l, r) = ([0] * n, [0] * n)
for i in range(n):
    (l0, r0) = map(int, input().split())
    (l[i], r[i]) = (l0, r0)
(u, v) = ([0] * m, [0] * m)
for i in range(m):
    (u0, v0) = map(int, input().split())
    (u[i], v[i]) = (u0 - 1, v0 - 1)
z = 2 * pow(10, 5) + 5
l1 = pow(2, (z + 1).bit_length())
l2 = 2 * l1
s0 = [0] * l2
for (u0, v0) in zip(u, v):
    l0 = max(l[u0], l[v0]) + l1
    r0 = min(r[u0], r[v0]) + l1
    while l0 <= r0:
        if l0 & 1:
            s0[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            s0[r0] += 1
            r0 -= 1
        r0 >>= 1
for i in range(1, l2):
    s0[i] += s0[i - 1]
now = [0] + list(s0)
tree = [-1] * now[l2]
for i in range(m):
    (u0, v0) = (u[i], v[i])
    l0 = max(l[u0], l[v0]) + l1
    r0 = min(r[u0], r[v0]) + l1
    while l0 <= r0:
        if l0 & 1:
            tree[now[l0]] = i
            now[l0] += 1
            l0 += 1
        l0 >>= 1
        if not r0 & 1 and l0 <= r0:
            tree[now[r0]] = i
            now[r0] += 1
            r0 -= 1
        r0 >>= 1
root = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]
ok = [0] * (n + 1)
ok[0] = 1
s0 = [0] + s0
st = []
now = 1
for i in range(s0[1], s0[2]):
    j = tree[i]
    unite(u[j], v[j], 1)
visit = [0] * l2
while now:
    if now >= l1 or visit[now << 1 ^ 1]:
        visit[now] = 1
        while st and st[-1][0] == now:
            undo(st.pop())
        now >>= 1
        continue
    now = now << 1 if not visit[now << 1] else now << 1 ^ 1
    for i in range(s0[now], s0[now + 1]):
        j = tree[i]
        unite(u[j], v[j], now)
ans = []
for i in range(n):
    if ok[i]:
        ans.append(i + 1)
sys.stdout.write(' '.join(map(str, ans)))