Nene and the Passing Game
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.
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$$$.
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$$$.
For each test case, output one integer — the minimum number of rounds of assessment Nene needs to complete her work.
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)))
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))
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)))