Nene and the Passing Game
Contest: Codeforces Round 939 (Div. 2)
Difficulty rating: 3000
Tags: constructive algorithms, data structures, dsu, graphs, sortings

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

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
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

Example output:
2
2
2
1
3

Editorial:
Let $$$L_j=\{i|i-r_i\le j\le i-l_i\},R_j=\{i|i-l_i\le j\le i+r_i\}$$$.
If $$$L_j$$$ and $$$R_j$$$ are both nonempty, then all players in both sets are connected (i.e. can pass the ball to each other).
Consider iterating $$$j$$$ from $$$1$$$ to $$$n$$$, and obtain $$$L$$$ and $$$R$$$ during the process. Player $$$i$$$ will enter $$$L$$$ when $$$j=i-r_i$$$, and will exit when $$$j=i-l_i+1$$$. Obtaining $$$R$$$ is similar.
If std::set in C++ is used, this will take $$$O(n\log n)$$$. It can be reduced to $$$O(n)$$$ with some simple tricks.
Then, we can use a disjoint-union set for the connectivity, and the problem is solved in $$$O(n\alpha(n))$$$.
Note that we can't afford to create $$$O(n^2)$$$ edges, so we can record the "root" in the disjoint-union set of each element instead of the elements themselves in sets $$$L,R$$$.