CF1119D Frets On Fire

Autream · 2025-08-18 20:05:06 · 题解

考虑先将矩阵的行按 s_i 从小到大排序，求出 \{s_n\} 的差分数组 \{c_n\}，容易发现每一行的贡献就是它与上一行相比多出的部分，也就是 \min \{c_i, r - l + 1\}（第一行的贡献为 r - l + 1）。

发现答案与 c_i 的顺序并无关联，于是考虑将 \{c_n\} 排序，二分出第一个 c_i > r - l + 1 的位置，用前缀和求解即可。

代码

CI N = 2e5 + 5;
int n, q, a[N], c[N], s[N];
signed main() {
    n = read();
    arrin(a, n);
    std::sort(arrall(a, n));
    rep(i, 1, n) c[i] = a[i] - a[i - 1];
    c[1] = 0;
    std::sort(arrall(c, n));
    rep(i, 1, n) s[i] = s[i - 1] + c[i];
    q = read();
    while(q --) {
        int l = read(), r = read(), ans = r - l + 1;
        int idx = std::l_b(arrall(c, n), r - l + 1) - c;
        ans += s[idx - 1] + (n - idx + 1) * (r - l + 1);
        printk(ans);
    }
    return 0;
}