P11830 [省选联考 2025] 幸运数字
题目描述
小 X 有 \(n\) 个正整数二元组 \((a_i, b_i) (1 \leq i \leq n)\)。他将会维护初始为空的可重集 \(S\)，并对其进行 \(n\) 轮操作。第 \(i (1 \leq i \leq n)\) 轮操作中，他会在 \(S\) 中加入 \(a_i\) 个 \(b_i\)。
设 \(m = \sum \limits_{i=1}^{n} a_i\)，在所有操作结束后，小 X 会得到一个包含 \(m\) 个正整数的可重集 \(S\)。最后他会计算 \(S\) 的中位数，即 \(S\) 中第 \(\left\lfloor \frac{m+1}{2} \right\rfloor\) 小的数，作为他的幸运数字。
想知道小 X 幸运数字的小 Y 不知道这 \(n\) 个二元组的具体数值是多少，但她得知了每个数的范围。具体地，对于每个 \(1 \leq i \leq n\)，小 Y 知道 \(a_i \in [l_{i,1}, r_{i,1}]\) 且 \(b_i \in [l_{i,2}, r_{i,2}]\)。
小 Y 想知道在满足以上条件的情况下，有多少个数可能成为小 X 的幸运数字。
输入格式
本题有多组测试数据。输入的第一行两个整数 \(c, T\)，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 \(c = 0\)。
对于每组测试数据，第一行一个整数 \(n\)，表示二元组的个数，接下来 \(n\) 行，第 \(i (1 \leq i \leq n)\) 行四个整数 \(l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}\)，描述二元组每个数的范围。
输出格式
对于每组测试数据，输出一行一个整数，表示可能的幸运数字个数。
输入输出样例 #1
输入 #1
0 4
2
1 2 1 1
1 1 2 2
2
1 1 1 2
1 1 2 3
2
1 2 1 2
2 3 3 4
4
1 2 1 4
3 4 1 2
3 4 2 3
3 4 3 4
输出 #1
1
2
4
3
说明/提示
【样例 1 解释】
该组样例共有 \(4\) 组测试数据。
- 对于第一组测试数据，若取 \((a_1, b_1) = (1, 1), (a_2, b_2) = (1, 2)\)，则得到 \(S = \{1, 2\}\)，其中位数为 \(1\)；若取 \((a_1, b_1) = (2, 1), (a_2, b_2) = (1, 2)\)，则得到 \(S = \{1, 1, 2\}\)，其中位数为 \(1\)。因此仅有 \(1\) 为可能计算出的中位数，因此答案为 \(1\)。
- 对于第二组测试数据，若取 \((a_1, b_1) = (1, 1), (a_2, b_2) = (1, 2)\)，则得到 \(S = \{1, 2\}\)，其中位数为 1；若取 \((a_1, b_1) = (1, 2), (a_2, b_2) = (1, 3)\)，则得到 \(S = \{2, 3\}\)，其中位数为 \(2\)。可以证明不存在其他可能计算出的中位数，因此答案为 \(2\)。
- 对于第三组测试数据，可以证明有且仅有 \(1, 2, 3, 4\) 为可能计算出的中位数，因此答案为 \(4\)。
- 对于第四组测试数据，可以证明有且仅有 \(1, 2, 3\) 为可能计算出的中位数，因此答案为 \(3\)。
【样例 2】
见选手目录下的 lucky/lucky2.in 与 lucky/lucky2.ans。
该组样例共有 \(60\) 组测试数据，所有数据均满足 \(n = 4\)。其中测试数据 \(1 \sim 20\) 满足特殊性质 AB，测试数据 \(21 \sim 40\) 满足特殊性质 A。
【样例 3】
见选手目录下的 lucky/lucky3.in 与 lucky/lucky3.ans。
该组样例共有 \(4\) 组测试数据，所有数据均满足 \(n = 2\,000\)。其中测试数据 \(1\) 满足特殊性质 AB，测试数据 \(2\) 满足特殊性质 A，测试数据 \(3\) 满足特殊性质 B。
【样例 4】
见选手目录下的 lucky/lucky4.in 与 lucky/lucky4.ans。
该组样例共有 \(2\) 组测试数据，所有数据均满足 \(n = 2 \times 10^5\)。其中测试数据 \(1\) 满足特殊性质 A，测试数据 \(2\) 满足特殊性质 B。
【子任务】
设 \(\sum n\) 为单个测试点内所有测试数据的 \(n\) 的和。对于所有测试点，
- \(1 \leq T \leq 400\)，
- \(1 \leq n \leq 2 \times 10^5\)，\(1 \leq \sum n \leq 6 \times 10^5\)，
- \(\forall 1 \leq i \leq n\)，\(1 \leq l_{i,1} \leq r_{i,1} \leq 10^9\)，\(1 \leq l_{i,2} \leq r_{i,2} \leq 10^9\)。
::cute-table{tuack}
| 测试点编号 | \(n \leq\) | \(\sum n \leq\) | 特殊性质 A | 特殊性质 B |
|---|---|---|---|---|
| \(1\) | \(4\) | \(400\) | 是 | 是 |
| \(2\) | ^ | ^ | ^ | 否 |
| \(3\) | \(2\,000\) | \(10^4\) | ^ | 是 |
| \(4\) | ^ | ^ | ^ | 否 |
| \(5\) | ^ | ^ | 否 | 是 |
| \(6\) | ^ | ^ | ^ | 否 |
| \(7\) | \(2 \times 10^5\) | \(6 \times 10^5\) | 是 | 是 |
| \(8\) | ^ | ^ | ^ | 否 |
| \(9\) | ^ | ^ | 否 | 是 |
| \(10\) | ^ | ^ | ^ | 否 |
- 特殊性质 A：\(\forall 1 \leq i \leq n\)，\(r_{i,1}, r_{i,2} \leq n\)。
- 特殊性质 B：\(\forall 1 \leq i \leq n\)，\(l_{i,1} = r_{i,1}\)。