#PQJ1929x10147. QOJ 1929_10147
QOJ 1929_10147
2025 联合省选 第一试幸运数字(lucky) 幸运数字(lucky) 【题目描述】 小X 有n 个正整数二元组(ai, bi) (1 ≤i ≤n)。他将会维护初始为空的可重集S, 并对其进行n 轮操作。第i (1 ≤i ≤n) 轮操作中,他会在S 中加入ai 个bi。 设m = !n i=1 ai,在所有操作结束后,小X 会得到一个包含m 个正整数的可重集 S。最后他会计算S 的中位数,即S 中第⌊m+1 2 ⌋小的数,作为他的幸运数字。 想知道小X 幸运数字的小Y 不知道这n 个二元组的具体数值是多少,但她得知了 每个数的范围。具体地,对于每个1 ≤i ≤n,小Y 知道ai ∈[li,1, ri,1] 且bi ∈[li,2, ri,2]。 小Y 想知道在满足以上条件的情况下,有多少个数可能成为小X 的幸运数字。 【输入格式】 从文件lucky.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行两个整数c, T,分别表示测试点编号和测试数 据组数,接下来输入每组测试数据。样例满足c = 0。 对于每组测试数据,第一行一个整数n,表示二元组的个数,接下来n 行,第 i (1 ≤i ≤n) 行四个整数li,1, ri,1, li,2, ri,2,描述二元组每个数的范围。 【输出格式】 输出到文件lucky.out 中。 对于每组测试数据,输出一行一个整数,表示可能的幸运数字个数。 【样例1 输入】 1 0 4 2 2 3 1 2 1 1 4 1 1 2 2 5 2 6 1 1 1 2 7 1 1 2 3 8 2 9 1 2 1 2 10 2 3 3 4 11 4 12 1 2 1 4 第2 页 共12 页
2025 联合省选 第一试幸运数字(lucky) 13 3 4 1 2 14 3 4 2 3 15 3 4 3 4 【样例1 输出】 1 1 2 2 3 4 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。其中测试数据1 ∼20 满足 特殊性质AB,测试数据21 ∼40 满足特殊性质A。 【样例3】 见选手目录下的lucky/lucky3.in 与lucky/lucky3.ans。 该组样例共有4 组测试数据,所有数据均满足n = 2, 000。其中测试数据1 满足特 殊性质AB,测试数据2 满足特殊性质A,测试数据3 满足特殊性质B。 第3 页 共12 页
2025 联合省选 第一试幸运数字(lucky) 【样例4】 见选手目录下的lucky/lucky4.in 与lucky/lucky4.ans。 该组样例共有2 组测试数据,所有数据均满足n = 2 × 105。其中测试数据1 满足 特殊性质A,测试数据2 满足特殊性质B。 【子任务】 设! n 为单个测试点内所有测试数据的n 的和。对于所有测试点, • 1 ≤T ≤400, • 1 ≤n ≤2 × 105,1 ≤! n ≤6 × 105, • ∀1 ≤i ≤n, 1 ≤li,1 ≤ri,1 ≤109, 1 ≤li,2 ≤ri,2 ≤109。 测试点编号 n ≤ ! n ≤ 特殊性质A 特殊性质B 1 4 400 是 是 2 否 3 2, 000 104 是 4 否 5 否 是 6 否 7 2 × 105 6 × 105 是 是 8 否 9 否 是 10 否 特殊性质A:∀1 ≤i ≤n, ri,1, ri,2 ≤n。 特殊性质B:∀1 ≤i ≤n, li,1 = ri,1。 第4 页 共12 页