#3706. 猜数字游戏的胜利者

猜数字游戏的胜利者

题目描述

Alex 和 Bob 一起玩一个叫“猜数字”的游戏。他们有一个密室,在密室的墙上挂着两个数字,整数 l 和 r(1 ≤ l ≤ r ≤ 109)。 Alex 负责在 [l, r] 区间内选一个数字,Bob 将尝试猜测 Alex 选的数字。

Alex 提供了一些线索让 Bob 来猜。这些线索是以区间对的方式提供的。一个区间对是一个有序的两位数字组 a = (a1, a2),满足 a1 < a2。如果 Alex 选择的数字 x 满足 a1 ≤ x ≤ a2,那么这个区间对就会给 Bob 提供一个“成功”的线索。否则,就是“失败”的线索。

Bob 将获得他能正确猜出的数字个数。现在,Alex 要求 Bob 猜出他心里的数字,但是 Bob 心理暗自抱怨,因为密室里只有两个数字。他想,在所有可能的心中数字中,有多少个数字是他能够以高于或者等于他平均正确的次数猜出来的?换句话说,Bob 想要知道,在所有可能的数字 x( l ≤ x ≤ r)中,有多少个 x 满足条件,即 x 能正确猜出的区间对数量大于或者等于 Bob 的平均正确次数。

由于数字的范围非常大,因此 Bob 忙得团团转。他请求你的帮助,希望你能够告诉他如何计算出最终的答案。

输入格式

输入的第一行包含两个用空格分隔的整数 l 和 r (1 ≤ l ≤ r ≤ 109) ——Alex 在密室里心选的数字的范围。

下一行包含一个整数 n (1 ≤ n ≤ 10 $${/}_{3}$$) ——提供给 Bob 的区间的数量。接下来 n 行每行都包含两个用空格分隔的整数 ai 和 bi (1 ≤ ai < bi ≤ 109) ——第 i 个区间的两个端点。这些区间按照亚历克斯提供的顺序给出的并不是密闭的,也就是说,他们可能重叠,也可能是不连续的。

当所有输入数据结束后,还会有第三行输入,内容为一个整数 m (1 ≤ m ≤ 109) ——Bob 心中想要猜的 Alex 的数字个数。

输出格式

输出一行包含单个整数 ——本题目的答案,用以表示在 [ l , r ] 范围内, Bob 能够正确猜出的数字个数。

这个数不包含任何加号或者空格。

样例

1 10
6
1 4
6 9
2 5
3 8
10 11
5 9
10 
10 
20 30
3
21 23
25 27
20 22
3 
0 

说明/提示

6 个区间对和数字 5 的情况

如第一种情况,有六个区间对 ( a 1 , a 2 )。数字 5 将会获得 4 个“成功”的线索,而 Bob 的平均正确次数是4。因此,在这个例子中,5 是正确的答案,因为它能够提供高于或者等于平均正确次数的线索。因此,在这个例子中,正确数字的个数就是 1。

在第二种情况下,数字 5 将会得到 2 个“成功”的线索,而 Bob 的平均正确次数是 2。因此,在这个例子中,正确的数字的个数是 0。

解析

解题思路

这道题的背景是一个猜数字游戏,Bob需要计算在给定的数字范围内,有多少个数字满足Bob猜中的区间对数量不小于 Bob 的平均正确次数。

首先,Bob的平均正确次数是每条区间对成功次数的平均。每条区间对的成功次数是如果Alex选择的数字x在这个区间[a1, a2]内,那么对于这条区间,x会得到一次成功。否则失败。

对于所有的可能的x,我们需要计算x在每个区间中出现的次数,然后判断这个次数是否 >= (n + 1)/2(因为平均数是n条区间成功的总和除以n,但在这里,Bob的平均正确次数就是成功区间对的数量的均值。Wait,Wait,Bob的平均正确次数是每条区间对是否成功的期望? Wait,不,Bob的平均正确次数是所有区间对成功次数的平均。例如,如果有6个区间,每个成功了4次,那么平均是4。Bob猜的正确的数字中有4个成功,所以4 >=4,算作有效。

Wait,Bob的平均正确次数是所有可能x中,每条区间成功的期望值。对于每条区间,成功的机会是该区间的长度与整个范围的比值。但Bob猜的x是某一个固定的数字,所以每条区间是否成功是根据x是否在区间内。但是,Bob的平均正确次数是所有x中,对于每个x,计算其在每个区间中的成功次数,然后取这些成功的平均值的均值。

Wait,这似乎是一个统计问题。Bob的平均正确次数是对于所有可能的x在[l, r]内,对于每个x,在所有区间中成功次数的平均。由于Bob选中的x是Alex心里的数字,而Alex心里的x是任意一个在[l, r]内的数字。Bob的平均正确次数实际上是,所有x在[l, r]内被选中的情况下,每条区间成功次数的均值。

更准确地说,对于所有的x,计算每个x在每个区间中是否成功,然后求和,再除以x的总数。因为x的总数是(r - l + 1)。

所以,对于每条区间(a1, a2),我们计算与之有重叠部分的x的数量。对于这个数量,每条区间对总的成功次数的贡献是max(0, min(a2, r) - max(a1, l) + 1)。因为对于这个区间,所有在 [max(a1, l), min(a2, r)] 范围内的x都会被认为是成功。所以,这条区间对的贡献是这段区间的长度。

Bob的平均正确次数是这些区间的总和除以x的总数 (r - l + 1) * n吗?Wait,不。每条区间是否成功,对于某个x,是0或1。但Bob的平均正确次数是所有可能x中,在每个区间上成功次数的平均。这等于,每条区间上成功的x的数量除以x的总数。因为,对于每条区间,成功x的数量是L = max(0, min(a2, r) - max(a1, l) + 1)。所以,每条区间对平均正确的贡献是 L / (r - l + 1)。Bob的平均正确次数是所有区间的 L_i 总和除以 (r - l + 1)。

Wait,不。对于每条区间,成功的x的数量是 L_i = max(0, min(a2, r) - max(a1, l) + 1)。那么,这些L_i的总和除以x的总数 (r-l+1) 才是Bob的平均正确次数。

所以,Bob的平均正确次数 = (sum over all intervals of L_i) / (r - l + 1)。

但 Bob 想要的是,他猜的x中有多少个 x 满足,在这些区间的成功次数 >= 这个平均值。

但平均值是 sum(L_i) / (r-l+1)。

所以,对于每个x,计算在给定的区间集中,x落在了多少个区间内。这个数字需要 >= average = sum(L_i) / (r-l+1)。

Wait,sum(L_i) 就是所有的区间的成功次数的总和。因为每条区间对所有在它范围内的x都贡献1分,所以 sum(L_i) 就是所有x在每个区间上成功次数的总和。

average = sum(L_i) / (r - l + 1)。

对于每个x,它的成功次数是 cnt[x]。Bob希望 cnt[x] >= average。

但 average 是 sum(L_i) / (r-l+1)。所以,cnt[x] >= (sum(L_i) ) / (r-l+1)。

由于 cnt[x] 是整数,sum(L_i) 也可能是整数,但 average 可能是小数。

例如,sum(L_i) = 10,x的总数是3。average = 10/3 ≈ 3.333。那么,如果x的cnt[x]是4,那么4 >=3.333,符合。

所以,对于每个x,如果 cnt[x] >= ceil(average)?或者,不,题意是 >= average,无论是否为整数。

因此,正确的x的数量是所有x中,cnt[x] >= (sum_L) / (r - l + 1) 的个数。

Wait,但 sum_L 是 sum(L_i)。sum_L 就是所有成功次数的总和。average = sum_L / total_x,其中 total_x = r - l + 1。

所以,对于每个x,cnt[x] 是 x 在每个区间内的情况数。例如,x在3个区间内,那么 cnt[x] = 3。average 就是 sum_L / total_x。

Bob希望 cnt[x] >= average。

由于 average 是 sum_L / total_x,这等价于 cnt[x] * total_x >= sum_L。

所以,对于每个x,if (cnt[x] * (r - l + 1) ) >= sum_L,则x是有效的。

这样可以避免浮点数运算,避免了精度问题。

因此,在代码中,sum_L 是 sum(L_i)。平均数的条件是 cnt[x] * total_x >= sum_L。

所以,正确的步骤是:

  1. 计算每个区间的 L_i,即 max(0, min(a2, r) - max(a1, l) + 1)。
  2. sum_L = sum(L_i)。
  3. total_x = r - l + 1。
  4. 对于每个x,在[l, r]内,计算 cnt[x](落在所有区间内的次数)。
  5. 如果 cnt[x] * total_x >= sum_L,则x是有效的。

这样可以避免浮点运算,提高效率,也避免了精度问题。

算法选择理由

  • 由于n可以大到1e3,而l和r可以大到1e9,所以需要高效地计算每个区间的重叠情况。
  • 对于每个区间 (a1, a2),其与 [l, r] 的交集是 [max(a1, l), min(a2, r)]。如果这个区间的长度为正,那么这个交集的长度就是 L_i。
  • 由于直接对每个x进行计数是不现实的(x可以有1e9种可能),所以需要使用前缀和数组。创建一个大小为 (r - l + 1) 的计数数组,但直接遍历每个区间并对其覆盖范围进行++操作是O(n + (r-l+1)),但当r-l+1达到1e9时,这会超出时间限制。

例如,在最坏的情况下,如果n=1e3,而r-l+1=1e9,那么代码的O(n + (r-l+1))是O(1e9)的,这在1秒内是无法运行的。

因此,需要一个更高效的方法。

解决方案

为了解决这个问题,我们需要计算每个x在区间中的出现次数。由于x的范围可能非常大,直接遍历每个x是不现实的。相反,可以使用差分数组的技术。

差分数组的技巧是创建一个 delta 数组,初始时全是0。对于每个区间 [A, B],我们在 delta[A - l] += 1,delta[B - l + 1] -= 1。然后,通过对delta数组进行前缀和计算,就可以得到每个x的cnt[x]。

例如,假设 l=1,r=10。对于区间 [3,5],我们在delta[2] +=1,delta[6] -=1。前缀和将对3-5的x的cnt[x]加1。

这样,我们就可以在O(n + (r-l+1))的时间内计算出每个x的cnt[x]。但当r-l+1达到1e9时,这仍然是O(1e9)的操作,这在1秒内是无法接受的。

然而,在本题中,n可以是1e3,而1e3 * 1e9是1e12,这显然是无法处理的。

Wait,但每个区间的处理是O(1)的。所以对于n=1e3个区间,处理这些区间的操作是O(n)的。但是,构建delta数组时,当r-l+1达到1e9时,创建一个大小为1e9的delta数组是 impossible的。

这显然是不可能的。因此,需要另一种方法。

Wait,但x的总数是 r - l + 1。假设这个数是1e9。那么,创建一个大小为1e9的向量是不现实的。因此,必须找到一种更有效的方法来计算每个x的cnt[x]。

这时,注意到对于每个区间的 [A,B],实际影响的x的范围是 max(A, l) 到 min(B, r)。所以,每个区间的实际影响范围是 [L, R],其中 L = max(a1, l),R = min(a2, r)。如果 L > R,那么这个区间没有影响。

那么,每个有效的区间的 [L, R] 范围内,所有x的cnt[x]都应增加1。

因此,问题是如何高效地表示这些区间,然后计算每个x落在了多少个区间内。

由于x的范围可能非常大,但n只有1e3,所以可能使用线段树或者差分数组,但当x的范围过大时,差分数组不适用。

这时,想到的是一种事件处理的方法。可以将所有的区间转换为L和R,然后对每个x,计算它位于多少个区间内。

然而,x的范围是 [l, r],而区间的数量是1e3,所以可能使用扫描线技术。

具体来说,可以将所有的区间按x排序,然后对于每个点x,计算当前有多少个区间包含了x。

但x的范围是1e9,不能遍历。需要找到一种方法,不遍历每个x,就能知道哪些x的cnt[x] * (r-l+1) >= sum_L。

Wait,sum_L 已经计算出来了,sum_L 是所有L_i的和。average = sum_L / (r-l+1)。

对于x的cnt[x],如果 cnt[x] * (r-l+1) >= sum_L,则x是有效的。

这等价于 cnt[x] >= average。

但average可能不是整数。例如,sum_L=5,total_x=2。average=2.5。那么任何cnt[x] >=3的x都是有效的。

但sum_L和total_x是已知的。sum_L是所有L_i的和,total_x = r - l +1。

因此,对于每个x,我们需要知道 cnt[x] 是多少,然后判断是否 >= (sum_L) / (total_x)。

由于x的范围可能非常大,直接计算每个x的cnt[x]并进行比较是不现实的。因此,需要找到所有满足 cnt[x] * total_x >= sum_L 的x的个数。

这等价于 cnt[x] >= ceil( sum_L / total_x ) if sum_L is not divisible by total_x. Otherwise, cnt[x] >= sum_L / total_x。

Wait,但平均数是 sum_L / total_x。x需要有 cnt[x] >= average。

例如,sum_L=5,total_x=3。average=5/3≈1.666。所以,cnt[x] >=2的x才会被算在内。

所以,这些x的cnt[x]是2或3。

因此,不等式是 cnt[x] * total_x >= sum_L。

这等价于 cnt[x] >= ceil( sum_L / total_x )。

因为 sum_L / total_x 可能是小数。ceil(sum_L / total_x) 就是最小的整数,使得 cnt[x] >= that value 时,cnt[x] * total_x >= sum_L。

例如,sum_L=5, total_x=3: ceil(5/3)=2。所以 cnt[x] >=2。

sum_L=6, total_x=3: ceil(6/3)=2。cnt[x] >=2 时,2*3=6=6,符合。

所以,正确的条件是 cnt[x] >= ceil( (sum_L) / (total_x) )。

但如何计算这些x的个数呢?

由于每个区间的处理是 [L, R],每个x的cnt[x]就是这些区间的数量。因此,问题转化为,找到所有x,使得在 [l, r] 范围内,x被包含在至少k个区间中,其中k = ceil( sum_L / total_x )。

但k的值可能从0到n。

如何计算这些x的个数呢?

这又是一个区间覆盖问题。每个区间的 [L, R] 内的x,其cnt[x]就是该x被包含在区间的数量。因此,需要找到所有x,使得它们被包含在 >=k 个区间中。

这个问题可以通过使用前缀 sums 或者差分数组来解决。但是,由于x的范围可能非常大,所以需要一种不使用显式数组的方法。

这时,可以将所有的区间 [A_i, B_i] 转换成 [L_i, R_i](即max(a1, l), min(a2, r)),然后对这些区间进行合并,计算出每个点x的覆盖次数,然后统计覆盖次数 >=k的点的个数。

但这些区间的数量可能有重叠,因此需要先对它们进行合并。然而,合并区间以计算覆盖次数的常规方法是O(n log n)的,这在n=1e3是可行的。

所以,以下是解决方案的步骤:

  1. 计算 sum_L 和 total_x。 sum_L 是所有 L_i = max(0, min(a2, r) - max(a1, l) + 1) 的和。如果 L >= R,则 L_i=0。

  2. 计算 k = ceil( sum_L / total_x )。 如果 sum_L <=0,那么k=0。但根据题意,每个区间 a1 < a2,所以 L_i >=0。sum_L是所有 L_i 的和,每个 L_i 都是 >=0的。但当 sum_L=0 时,可能没有区间。但根据n的下界是1,但n可以为1。例如,n=1,a1=2, a2=3。如果 l=1, r=1,那么 L_i = max(2, 1) =2,min(3,1)=1。由于 a1 < a2,但 L_i 可能是0。Wait,当 a1 >= l 且 a2 <= r 时,L_i = a1 <= a2,但 a1 < a2,所以 L_i >=1。

Wait,a1 < a2 是给定的。但是,max(a1, l) 可能等于 a1(如果 a1 >= l),或者等于 l(如果 a1 < l)。同理,min(a2, r) 可能等于 a2(a2 <=r),或者r(a2 > r)。

所以,L_i = max(0, min(a2, r) - max(a1, l) + 1)。如果 max(a1, l) > min(a2, r),则 L_i=0。

所以 sum_L 可以为0。

  1. 计算k。当 sum_L=0 时,k=0。因此,所有x都满足 cnt[x] >=0。由于 cnt[x] 是 >=0的,所以所有的x都有效。但是,sum_L=0 也意味着没有区间的成功,平均数是0。所以,x需要有 cnt[x] >=0,即所有x都有效。

在这种情况下,答案是 (r - l +1)。

否则,k = ceil( sum_L / total_x )。

  1. 现在,我们需要计算有多少x在 [l, r] 内,且 x 被包含在 >=k 个区间中。

每个区间的 [L_i, R_i] 是 [max(a1, l), min(a2, r)]。如果 L_i > R_i,这个区间被忽略。

所以,步骤3是生成所有的有效区间 [L_i, R_i]。

  1. 合并这些区间,并计算每个点的覆盖次数。

  2. 使用扫描线技术,统计覆盖次数 >=k 的x的个数。

由于 x 的范围是 [l, r],而区间的数量是 n=1e3,所以可以使用差分数组的方法。创建一个差分数组 events,对于每个区间 [L, R],在 L 位置+1,在 R+1 位置-1。然后,通过扫描 events 数组,计算出每个点的覆盖次数。

但是,当 l 和 r 的范围是1e9时,直接创建一个差分数组是不可能的。因此,需要使用事件驱动的方法,记录所有的开始和结束点,然后对这些事件进行排序,计算每个区间的覆盖次数。

具体来说,可以使用以下步骤:

a. 收集所有的事件。对于每个有效区间 [L, R],添加 (L, +1) 和 (R+1, -1) 两个事件。 b. 这些事件按照x的顺序进行排序。 c. 遍历这些事件,跟踪当前的覆盖次数。 d. 在事件之间,即在prev_x和current_x之间,如果覆盖次数 >=k,则计算这个区间的x的个数。

e. 例如,假设有两个事件 (x1, delta1) 和 (x2, delta2)。之间的区间是 [x1, x2-1]。在这个区间内,覆盖次数是current_count。如果current_count >=k,那么这个区间的长度 (x2 - x1) 就是有效x的个数。

因此,这可以有效地计算出所有满足条件的x的个数,而不需要遍历1e9的x。

复杂度分析

  • 时间复杂度:

    • 计算 sum_L: O(n)。
    • 计算k: O(1)。
    • 生成事件: O(n)。
    • 对事件进行排序: O(n log n)。
    • 遍历事件: O(n)。 因此,总的时间复杂度是 O(n log n),适合n=1e3的规模。
  • 空间复杂度:

    • 事件数组的大小是2n,适合n=1e3。

代码实现

  1. 读取 l, r, n。
  2. 读取n个区间的a1, a2。
  3. 计算sum_L和total_x。 sum_L = sum over all L_i,其中L_i = max(0, min(a2, r) - max(a1, l) + 1)。 total_x = r - l + 1。
  4. 计算k = ceil( sum_L / total_x )。当 sum_L ==0 时,k=0。
  5. 生成事件列表。对于每个区间,计算L_i和R_i,如果 L_i <= R_i,添加 (L_i, +1) 和 (R_i +1, -1)。
  6. 对事件列表按x排序。
  7. 遍历事件,跟踪current_count,prev_x。初始时current_count=0, prev_x = l -1。
  8. 对于每个事件 (x, delta):
    • 在prev_x +1 到 x-1的区间内,current_count是之前的值。如果这个区间的长度 >0,计算是否有效。
    • 更新current_count。
    • 更新prev_x为x。
  9. 最后,检查是否还有未处理的事件 after last event。

在代码中,需要特别注意当事件列表为空时的情况。但当sum_L=0时,k=0,所有x都有效。所以,当k=0时,答案是total_x。

代码示例

以下是C++代码的实现。

{ 

## 来源
AI 生成 · olympiccoder:7b · 提高 · 二分答案