解题思路
由题意知, 每次观测完Iris都会把区间二等分, 易知左边区间和右边区间的幸运点一一对应$^{\text{†}}$, 且值右区间每个幸运点分别减去左区间对应的幸运点都等于中值.所以每次只需求左区间幸运点值之和和幸运点数量,并由此求出右区间幸运点值之和,两者相加即为答案.( 如当前区间为奇数长度, 还需加上中点值) 时间复杂度为$O(n)$.
$^{\text{†}}$两区间的幸运点一一对应, 即对于区间$a$上的任意幸运点$a_i$, 在区间$b$上存在对应的幸运点$b_i$, 反之亦然.
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| import sys
sys.setrecursionlimit(114514)
def check(start: int, end: int, k: int) -> tuple[int, int]: """ 检查当前区间的所有幸运点和幸运点数量. """ if end - start + 1 < k: return 0, 0
mid = (start + end) // 2 luck = mid if (start - end + 1) % 2 == 1 else 0
l_rst, l_luck_point = check(start, mid + (-1 if luck else 0), k) r_rst = l_rst + mid * l_luck_point
return ( l_rst + r_rst + luck, 2 * l_luck_point + (1 if luck else 0), )
for _ in range(int(input())): n, k = map(int, input().split()) print(check(1, n, k)[0])
|