题解：P13826 [Ynoi Easy Round 2026] 寒蝉鸣泣之时

· · 题解

Easy Round 还是比较善良的

题目相当于是矩形加，求有多少个点值为 x，x 是 m 的倍数。

首先这东西是无法直接做的，考虑将矩阵加离线下来做扫描线。那么有 n 次区间加，\frac{n^2}{m} 次查询，可以联想到分块，但是发现单次 O(1) 并不好做，我自己就只能想到这了。

看了其他题解后，我们可以转换思路，发现可以不对每个 m 的倍数 x 查询答案，而是在散块修改时对每个块重构统计答案。但我们又发现了一个问题，因为单次暴力重构是 O(\frac{n}{m}\sqrt{n})=O(n) 的，而我们每次散块修改都要重构，散块会修改 n 次，所以一共会重构 n 次，时间复杂度就炸了。但我们发现真正可能会对答案产生贡献的 x 其实很少，我们可以维护一个块的最大最小值，x 一定在这个范围内。

设 k 为区间最大值减区间最小值，我们此时重构一次的复杂度时 O(\frac{k}{m}\sqrt{n})=O(k)。对于每个块，因为操作只有加减 1，所以一个块内的极差最大只有 n，因此总的复杂度时 O(n\sqrt{n}) 的。

到这里思路就讲完了，但是 Ynoi 的题是不会让你这么轻松的通过的。直接开 n\sqrt{n} 的数组空间会不够用，但不会超很多，而逐块处理又会被卡常。这里就有两种做法，一种是可以开一个 short 和一个 char 用来代替 int，是够表示的。或者分成几次处理，可能需要稍微卡卡常数。然后记得最后处理一次。最后放上卡常前的代码。

inline void rebuild(int x) {
    if (mn[x] <= mx[x]) {
        for (int i = L[x]; i <= R[x]; i ++) {
            //-tag + m * t = v
            //-tag = v - m * t
            //m * r <= v - mn
            //m * l >= v - mx
            int v = a[i];
            for (int j = max(1, (v - mx[x] + m - 1) / m); j <= min(k, (v - mn[x]) / m); j ++) {
                ans[j] += sum[x][N + v - j * m];
            }
        }
        for(int i = mn[x];i <= mx[x];i ++)sum[x][i + N] = 0;
        mx[x] = -inf, mn[x] = inf;
    }
}
inline void add(int l, int r, int x) {
    if (pos[l] == pos[r]) {
        rebuild(pos[l]);
        for (int i = l; i <= r; i ++)a[i] += x;
    } else {
        rebuild(pos[l]);
        rebuild(pos[r]);
        for (int i = l; i <= R[pos[l]]; i ++)a[i] += x;
        for (int i = pos[l] + 1; i <= pos[r] - 1; i ++)tag[i] += x;
        for (int i = L[pos[r]]; i <= r; i ++)a[i] += x;
    }
}
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    block = sqrt(n);
    tot = (n + block - 1) / block;
    L[1] = 1, R[tot] = n;
    for (int i = 2; i <= tot; i ++) L[i] = min(L[i - 1] + block, n);
    for (int i = 1; i < tot; i ++) R[i] = L[i + 1] - 1;
    for (int i = 1; i <= tot; i ++)for (int j = L[i]; j <= R[i]; j ++)pos[j] = i;
    k = n / m;
    for(int i = 1;i <= tot;i ++) mx[i] = -inf,mn[i] = inf;
    for (int i = 1; i <= n; i ++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        E[a].push_back({c, d - 1, 1});
        E[b].push_back({c, d - 1, -1});
    }
    for (int i = 1; i <= n; i ++) {
        for (auto p : E[i])add(p.l, p.r, p.x);
        for (int j = 1; j <= tot; j ++)sum[j][N - tag[j]], mn[j] = min(mn[j], -tag[j]), mx[j] = max(mx[j], -tag[j]);
    }
    for(int i = 1;i <= tot;i ++)rebuild(i);
    //最后记得处理
    for(int i = 1;i <= k;i ++)cout << ans[i] << '\n';
    return 0;
}