Nene and the Passing Game (Codeforces 1956F)
Tags: Others, dsu

Nene is training her team as a basketball coach. Nene's team consists of $$$n$$$ players, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th player has an arm interval $$$[l_i,r_i]$$$. Two players $$$i$$$ and $$$j$$$ ($$$i \neq j$$$) can pass the ball to each other if and only if $$$|i-j|\in[l_i+l_j,r_i+r_j]$$$ (here, $$$|x|$$$ denotes the absolute value of $$$x$$$).Nene wants to test the cooperation ability of these players. In order to do this, she will hold several rounds of assessment.  In each round, Nene will select a sequence of players $$$p_1,p_2,\ldots,p_m$$$ such that players $$$p_i$$$ and $$$p_{i+1}$$$ can pass the ball to each other for all $$$1 \le i < m$$$. The length of the sequence $$$m$$$ can be chosen by Nene. Each player can appear in the sequence $$$p_1,p_2,\ldots,p_m$$$ multiple times or not appear in it at all.  Then, Nene will throw a ball to player $$$p_1$$$, player $$$p_1$$$ will pass the ball to player $$$p_2$$$ and so on... Player $$$p_m$$$ will throw a ball away from the basketball court so it can no longer be used. As a coach, Nene wants each of $$$n$$$ players to appear in at least one round of assessment. Since Nene has to go on a date after school, Nene wants you to calculate the minimum number of rounds of assessment needed to complete the task.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$). The description of test cases follows.The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^6$$$) — the number of players.The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1\leq l_i\leq r_i\leq n$$$) — the arm interval of the $$$i$$$-th player.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^6$$$.

Output: For each test case, output one integer — the minimum number of rounds of assessment Nene needs to complete her work.

Note: In the first two test cases, Nene can host two rounds of assessment: one with $$$p=[1]$$$ and one with $$$p=[2]$$$. It can be shown that hosting one round of assessment is not enough, so the answer is $$$2$$$.In the third test case, Nene can host two rounds of assessment: one with $$$p=[1,3]$$$ and one with $$$p=[2]$$$. Player $$$1$$$ can pass the ball to player $$$3$$$ as $$$|3-1|=2 \in [1+1,3+3]$$$. It can be shown that hosting one round of assessment is not enough, so the answer is $$$2$$$.

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

Sample Outputs:
2
2
2
1
3

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

def f(u, v):
    return u << 24 ^ v

def get_root(s):
    if s ^ r[s]:
        r[s] = get_root(r[s])
        return r[s]
    return s

def unite(s, t):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return 0
    if r[s + n] < r[t + n]:
        (s, t) = (t, s)
    if r[s + n] == r[t + n]:
        r[s + n] += 1
    r[t] = s
    return 1
t = int(input())
ans = []
inf = pow(10, 15) + 1
for _ in range(t):
    n = int(input())
    (x, y, ma0) = ([0] * (2 * n), [0] * (2 * n), [0] * (2 * n))
    n3 = 3 * n
    for i in range(n):
        (l, r) = map(int, input().split())
        (x[2 * i], x[2 * i + 1]) = (f(l + i + n3, 2 * i), f(-l + i + n3, 2 * i + 1))
        (y[2 * i], y[2 * i + 1]) = (f(-r - i + n3, 2 * i), f(r - i + n3, 2 * i + 1))
    x.sort()
    y.sort()
    for i in range(2 * n):
        x[i] &= 16777215
    p = [0] * (2 * n)
    r = [i for i in range(n)] + [1] * n
    c = 0
    for i in y:
        j = i & 16777215
        if not j & 1:
            c += 1
        p[j] = c
    ma = -inf
    for i in range(2 * n - 1, -1, -1):
        j = x[i]
        if j & 1:
            ma = max(ma, p[j])
        else:
            ma0[i] = ma
    (mi, k) = (inf, -1)
    ans0 = n
    for (i, ma) in zip(x, ma0):
        pi = p[i]
        if not i & 1:
            if mi >= pi:
                if k ^ -1 and ma >= mi:
                    ans0 -= unite(i >> 1, k >> 1)
                (mi, k) = (pi, i)
            if ma >= pi:
                ans0 -= unite(i >> 1, k >> 1)
        elif mi <= pi:
            ans0 -= unite(i >> 1, k >> 1)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin

class DSU:

    def __init__(self, n):
        self.p = list(range(n))
        self.s = [1] * n

    def get_repr(self, elem):
        path = []
        while elem != self.p[elem]:
            path.append(elem)
            elem = self.p[elem]
        for x in path:
            self.p[x] = elem
        return elem

def solve(lefts, rights):
    n = len(lefts)
    next_left = [-1] * n
    next_right = [-1] * n
    for (i, l, r) in zip(range(n), lefts, rights):
        if i > l:
            (a, b) = (max(0, i - r), i - l)
            next_left[a] = max(next_left[a], b)
        if i + l < n:
            (a, b) = (i + l, min(i + r, n - 1))
            next_right[a] = max(next_right[a], b)
    for i in range(1, n):
        next_left[i] = max(next_left[i], next_left[i - 1])
        next_right[i] = max(next_right[i], next_right[i - 1])
    prev_good = [-1] * n
    for i in range(1, n):
        if next_left[i] >= i and next_right[i] >= i:
            prev_good[i] = i
        else:
            prev_good[i] = prev_good[i - 1]
    next_good = [n] * n
    for i in reversed(range(n - 1)):
        if next_left[i] >= i and next_right[i] >= i:
            next_good[i] = i
        else:
            next_good[i] = next_good[i + 1]
    del next_left, next_right
    next_end = [-1] * n
    result = 0
    parent = list(range(n))
    size = [1] * n
    path = []

    def get_repr(elem):
        while elem != parent[elem]:
            path.append(elem)
            elem = parent[elem]
        for x in path:
            parent[x] = elem
        path.clear()
        return elem

    def join(a, b):
        a = get_repr(a)
        b = get_repr(b)
        if a == b:
            return False
        if size[a] < size[b]:
            (a, b) = (b, a)
        size[a] += size[b]
        parent[b] = a
        return True
    for (i, l, r) in zip(range(n), lefts, rights):
        prev_a = None
        for (t, a, b) in [(0, max(0, i - r), i - l), (1, i + l, i + r)]:
            if b <= 0 or a >= n:
                continue
            a = next_good[max(0, a)]
            b = prev_good[min(n - 1, b)]
            if a > b:
                continue
            if prev_a is not None:
                join(a, prev_a)
            next_end[a] = max(next_end[a], b)
            prev_a = a
        if prev_a is None:
            result += 1
    del next_good, prev_good
    for i in range(1, n):
        next_end[i] = max(next_end[i - 1], next_end[i])
        if next_end[i] > i:
            join(i, i + 1)
    result += sum((i == p and ne >= i for (i, p, ne) in zip(range(n), parent, next_end)))
    return result
n_tests = int(stdin.readline())
for test_id in range(n_tests):
    n = int(stdin.readline())
    (lefts, rights) = ([], [])
    for i in range(n):
        (l, r) = (int(w) for w in stdin.readline().split())
        lefts.append(l)
        rights.append(r)
    print(solve(lefts, rights))

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

def f(u, v):
    return u << 24 ^ v

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

def unite(s, t):
    (s, t) = (get_root(s), get_root(t))
    if s == t:
        return
    root[s] = t
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
t = int(input())
ans = []
inf = pow(10, 15) + 1
for _ in range(t):
    n = int(input())
    (x, y, ma0) = ([0] * (2 * n), [0] * (2 * n), [0] * (2 * n))
    n3 = 3 * n
    for i in range(n):
        (l, r) = map(int, input().split())
        (x[2 * i], x[2 * i + 1]) = (f(l + i + n3, 2 * i), f(-l + i + n3, 2 * i + 1))
        (y[2 * i], y[2 * i + 1]) = (f(-r - i + n3, 2 * i), f(r - i + n3, 2 * i + 1))
    x.sort()
    y.sort()
    for i in range(2 * n):
        x[i] &= 16777215
        y[i] &= 16777215
    p = [0] * (2 * n)
    root = [i for i in range(n)]
    c = 0
    for i in y:
        if not i & 1:
            c += 1
        p[i] = c
    ma = -inf
    for i in range(2 * n - 1, -1, -1):
        j = x[i]
        if j & 1:
            ma = max(ma, p[j])
        else:
            ma0[i] = ma
    (mi, k) = (inf, -1)
    for (i, ma) in zip(x, ma0):
        pi = p[i]
        if not i & 1:
            if mi >= pi:
                if k ^ -1 and ma >= mi:
                    unite(i >> 1, k >> 1)
                (mi, k) = (pi, i)
            if ma >= pi:
                unite(i >> 1, k >> 1)
        elif mi <= pi:
            unite(i >> 1, k >> 1)
    ans0 = 0
    for i in range(n):
        if get_root(i) == i:
            ans0 += 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))