↓Skip to main content
  1. Posts/

CodeForces-2019B All Pairs Segments

·1 min·
Table of Contents

CodeForces-2019B All Pairs Segments #

Solution 1 #

落在 $a_i$ 的点被覆盖了 $(i+1)(n-i)-1$ 次 (减去了 $i=j$ 的特殊情况) 这样的点有 $1$ 个; 落在 $(a_i, a_{i+1})$ 的点被覆盖了 $(i+1)(n-i-1)$ 次, 这样的点有 $a_{i+1} - a_{i} - 1$ 个.

代码如下:

from collections import defaultdict

if __name__ == '__main__':
    t = int(input())
    while t > 0:
        t -= 1
        tmp = list(map(int, input().split()))
        n, q = tmp[0], tmp[1]
        a = list(map(int, input().split()))
        book = defaultdict(int)
        for i in range(n):
            book[(i + 1) * (n - i) - 1] += 1
            if i < n - 1:
                book[(i + 1) * (n - i - 1)] += a[i + 1] - a[i] - 1
        qs = list(map(int, input().split()))
        for k in qs:
            print(book[k], end=" ")
        print('')