UOJ Logo Universal Online Judge

UOJ

#952. 【统一省选2025】幸运数字

附件下载 统计

小 X 有 n 个正整数二元组 (ai,bi)(1in)。他将会维护初始为空的可重集 S,并对其进行 n 轮操作。第 i(1in) 轮操作中,他会在 S 中加入 aibi

m=i=1nai,在所有操作结束后,小 X 会得到一个包含 m 个正整数的可重集 S。最后他会计算 S 的中位数,即 S 中第 m+12 小的数,作为他的幸运数字。

想知道小 X 幸运数字的小 Y 不知道这 n 个二元组的具体数值是多少,但她得知了每个数的范围。具体地,对于每个 1in,小 Y 知道 ai[li,1,ri,1]bi[li,2,ri,2]

小 Y 想知道在满足以上条件的情况下,有多少个数可能成为小 X 的幸运数字。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,T,分别表示测试点编号和测试数据组数,接下来输入每组测试数据。样例满足 c=0

对于每组测试数据,第一行一个整数 n,表示二元组的个数,接下来 n 行,第 i(1in) 行四个整数 li,1,ri,1,li,2,ri,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 组测试数据。

  • 对于第一组测试数据,若取 (a1,b1)=(1,1),(a2,b2)=(1,2),则得到 S={1,2},其中位数为 1;若取 (a1,b1)=(2,1),(a2,b2)=(1,2),则得到 S={1,1,2},其中位数为 1。因此仅有 1 为可能计算出的中位数,因此答案为 1
  • 对于第二组测试数据,若取 (a1,b1)=(1,1),(a2,b2)=(1,2),则得到 S={1,2},其中位数为 1;若取 (a1,b1)=(1,2),(a2,b2)=(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。其中测试数据 120 满足特殊性质 AB,测试数据 2140 满足特殊性质 A。

【样例 3】

见选手目录下的 lucky/lucky3.in 与 lucky/lucky3.ans。

该组样例共有 4 组测试数据,所有数据均满足 n=2000。其中测试数据 1 满足特殊性质 AB,测试数据 2 满足特殊性质 A,测试数据 3 满足特殊性质 B。

【样例 4】

见选手目录下的 lucky/lucky4.in 与 lucky/lucky4.ans。

该组样例共有 2 组测试数据,所有数据均满足 n=2×105。其中测试数据 1 满足特殊性质 A,测试数据 2 满足特殊性质 B。

【子任务】

n 为单个测试点内所有测试数据的 n 的和。对于所有测试点,

  • 1T400
  • 1n2×1051n6×105
  • 1in1li,1ri,11091li,2ri,2109
测试点编号 n n 特殊性质 A 特殊性质 B
1 4 400
2 4 400
3 2000 104
4 2000 104
5 2000 104
6 2000 104
7 2×105 6×105
8 2×105 6×105
9 2×105 6×105
10 2×105 6×105
  • 特殊性质 A:1inri,1,ri,2n
  • 特殊性质 B:1inli,1=ri,1

时间限制:1s

空间限制:512MB