CF2019B All Pairs Segments 题解

SpringFullGarden · 2024-10-03 20:03:54 · 题解

题意

在数轴上有 n 个点，每两个点形成一个线段。

每次查询，有有几个点恰好被 k 个线段覆盖。

思路

观察下图。

可以发现，以第 i 个点为左端点的线段有 n - i 条，覆盖第 i 个点且不以第 i 个点位左端点的线段有 (n - i + 1)(i - 1) 条（i 左边有 i - 1 个点，每个点能覆盖到第 i 个点的线段有 n - i + 1 条）。

整理得，覆盖了第 i 个点的线段有 i\cdot (n - i + 1) - 1 条。

再考虑点不是给定的点。对于一个点，设它右边的第一个给定点是第 i 个点。发现除了以第 i 个点为左端点的线段以外，覆盖了第 i 个点的线段都覆盖了这个点。所以覆盖了这个点的线段有 (n - i + 1)(i - 1) 条。

枚举 i(1 \le i \le n)，算出有几条线段覆盖了第 i 个点。

再枚举 i(1 < i \le n)，算出它与前一个点之间的点被几条线段覆盖。

代码

ll a[200005], b[200005];
map <ll, ll> c;

signed main() {
    for(ll T = rd(); T--; ) {
        ll n = rd(), Q = rd();
        for(ll i = 1; i <= n; i++) a[i] = rd();
        c.clear();
        for(ll i = 1; i <= n; i++) b[i] = (n - i + 1) * i - 1, c[b[i]]++;
        for(ll i = 2; i <= n; i++)
            c[b[i] - (n - i)] += a[i] - a[i - 1] - 1;
        while(Q--) {
            ll x = rd();
            cout << c[x] << ' ';
        }
        puts("");
    }
    return 0;
}