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

· · 题解

本质简单题，适合分块入门。

Solution

做过 P5490 【模板】扫描线 & 矩形面积并 的都知道，这个题目明显是对着 x 进行扫描线，数据结构维护 y。

我们思考选取哪种数据结构，显然线段树并不可行，她无法维护每个点数值出现的次数。

做过 P4168 [Violet] 蒲公英 的都知道，分块可以轻松维护这种信息，n \le 3 \times 10^5 我会分块！

首先扫描线的思想，我们需要区间 +1 和区间 -1，还要维护每个数出现的个数并按 m 的整数倍统计 res_i（表示 i \times m 的次数），因此我们应该在每次修改出现时修改 res。

再考虑怎么记录词频，我们这样定义 cnt_{B,a_i} 表示第 B 个块 a_i 的词频。特别的，由于我们使用的懒标记，故 a_i 可能为负数，因此存储时我们存储 a_i-mn_B 即减去块内最小值。

考虑答案的更新，我们实则只需要更新块内 mn_B\le a_i\le mx_B 的所有 a_i 即可，总更新次数为 \frac{mx_B-mn_B}{m} 由于 mx_B-mn_B\le n，m \ge \sqrt n，因此复杂度是 O(\sqrt n)

总复杂度 O(n \times \sqrt n)。

注意卡常🤔。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
const int N = 3e5+10;
const int B = 550;
const int INF = 1e9;
int n, m;
int bel[N], cntb, L[N], R[N];
short cnt[B + 5][N];
long long ans[N], res[N];
int a[N];
int mn[B + 5], mx[B + 5], lz[B + 5];
struct nod {
    int l, r, f;
};
vector<nod>e[N];
void clear(int x) {
    int mmn = mn[x] + lz[x], mmx = mx[x] + lz[x];
    for (int i = (mmx / m) * m; i >= mmn; i -= m) res[i / m] -= cnt[x][i - mmn];
    rep(i, L[x], R[x]) cnt[x][a[i] - mn[x]]--;
}
void rebuild(int x) {
    mx[x] = -INF, mn[x] = INF;
    rep(i, L[x], R[x]) mn[x] = min(mn[x], a[i]), mx[x] = max(mx[x], a[i]);
    rep(i, L[x], R[x]) cnt[x][a[i] - mn[x]]++;
    int mmn = mn[x] + lz[x], mmx = mx[x] + lz[x];
    for (int i = (mmx / m) * m; i >= mmn; i -= m) res[i / m] += cnt[x][i - mmn];
}
void renew(int x, int v) {
    int mmn = mn[x] + lz[x], mmx = mx[x] + lz[x];
    for (int i = (mmx / m) * m; i >= mmn; i -= m)res[i / m] -= cnt[x][i - mmn];
    lz[x] += v;
    int nmn = mmn + v, nmx = mmx + v;
    for (int i = (nmx / m) * m; i >= nmn; i -= m)res[i / m] += cnt[x][i - nmn];
}
void update(int l, int r, int v) {
    int x = bel[l], y = bel[r];
    if (x == y) {
        clear(x);
        rep(i, l, r) a[i] += v;
        rebuild(x);
        return;
    }
    clear(x);
    rep(i, l, R[x]) a[i] += v;
    rebuild(x);
    rep(i, x + 1, y - 1) renew(i, v);
    clear(y);
    rep(i, L[y], r) a[i] += v;
    rebuild(y);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    int blo = sqrt(n) + 1;
    rep(i, 1, n) {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;
        e[x1].push_back({y1, y2 - 1, 1});
        e[x2].push_back({y1, y2 - 1, -1});
    }
    cntb = (n + blo - 1) / blo;
    rep(i, 1, n) bel[i] = (i + blo - 1) / blo;
    rep(i, 1, cntb) L[i] = (i - 1) * blo + 1, R[i] = min(i*blo, n), cnt[i][0] = R[i] - L[i] + 1;
    rep(i, 1, n) {
        for (auto [l, r, x] : e[i]) update(l, r, x);
        rep(j, 1, n / m) ans[j] += res[j];
    }
    rep(i, 1, n / m) cout << ans[i] << '\n';
    return 0;
}