1064 字
5 分钟
AtCoder Beginner Contest 477 F:Count Cells in a Window
树状数组维护区间和-1791116082410

AtCoder Beginner Contest 477 F:Count Cells in a Window#

题目重述#

给定一个 NN 行 MM 列的网格。第 ii 行中,第 LiL_i 列到第 RiR_i 列的格子为黑色,其余格子为白色。

每次查询给出 A,B,C,DA,B,C,D,求矩形区域

[A,B]×[C,D][A,B]\times[C,D]

内黑色格子的数量。

约束为 1≤N,M,Q≤2×1051\le N,M,Q\le 2\times 10^5,且 1≤Li≤Ri≤M1\le L_i\le R_i\le M。

关键观察#

固定扫描到前 ii 行,令 cover[x] 表示第 xx 列在这些行中出现的黑格数量,则查询前缀行区间 [1,i][1,i] 对列区间 [C,D][C,D] 的答案就是

∑x=CDcover[x].\sum_{x=C}^{D}\text{cover}[x].

加入第 ii 行时,需要对整个区间 [Li,Ri][L_i,R_i] 加 11;查询时需要求列区间和。因此问题转化为:

  • 区间加:对 [Li,Ri][L_i,R_i] 中每个位置加 11;
  • 区间求和:求 [C,D][C,D] 的元素和。

单棵树状数组适合“单点修改、前缀和查询”,不能直接同时完成区间加和区间求和。使用两棵树状数组维护差分数组即可支持这两种操作。

解析#

两棵树状数组维护区间加、区间和#

设对差分数组在位置 ll 加上 kk、在位置 r+1r+1 加上 −k-k。令第一棵树状数组维护这些差分值,第二棵树状数组维护差分值乘以位置偏移后的结果:

tr1[l]+=k,tr1[r+1]−=k,tr2[l]+=k(l−1),tr2[r+1]−=kr.\begin{aligned} \text{tr}_1[l]&\mathrel{+}=k, &\text{tr}_1[r+1]&\mathrel{-}=k,\\ \text{tr}_2[l]&\mathrel{+}=k(l-1), &\text{tr}_2[r+1]&\mathrel{-}=kr. \end{aligned}

记两棵树状数组在位置 xx 的前缀和分别为 S1(x)S_1(x)、S2(x)S_2(x),则原数组的前缀和为

prefix⁡(x)=xS1(x)−S2(x).\operatorname{prefix}(x)=xS_1(x)-S_2(x).

所以区间和可以写成

sum⁡(l,r)=prefix⁡(r)−prefix⁡(l−1).\operatorname{sum}(l,r)=\operatorname{prefix}(r)-\operatorname{prefix}(l-1).

代码中的 modify(l, r, k) 实现区间加,query_interval(l, r) 实现区间求和。

按行编号离线处理查询#

设一个查询为 (A,B,C,D)(A,B,C,D)。扫描行编号 ii 时:

  • 在处理第 AA 行之前,树状数组维护的是第 11 到第 A−1A-1 行,因此记录一次负贡献;
  • 加入第 AA 行到第 BB 行后,树状数组维护的是第 11 到第 BB 行,因此记录一次正贡献。

两次前缀状态之差恰好只保留第 AA 到第 BB 行的贡献。代码使用 enter[A] 保存负贡献事件,使用 settle[B] 保存正贡献事件:

answer(A,B,C,D)=F(B,C,D)−F(A−1,C,D),\text{answer}(A,B,C,D) =F(B,C,D)-F(A-1,C,D),

其中 F(i,C,D)F(i,C,D) 表示前 ii 行在列区间 [C,D][C,D] 中的黑格数。

正确性说明#

在扫描到第 ii 行后,树状数组中每一列的值等于前 ii 行该列黑格的数量,因为每行只在自己的黑色区间 [Li,Ri][L_i,R_i] 上加 11。因此 query_interval(C, D) 等于前 ii 行在列区间 [C,D][C,D] 内的黑格总数。

对于查询 (A,B,C,D)(A,B,C,D),负事件发生在加入第 AA 行前,得到 F(A−1,C,D)F(A-1,C,D);正事件发生在加入第 BB 行后,得到 F(B,C,D)F(B,C,D)。两者相减后,编号不在 [A,B][A,B] 内的行贡献完全抵消,剩余值正是目标矩形中的黑格数量。

每次区间修改或区间查询需要 O(log⁡M)O(\log M) 时间,所有行和查询的总复杂度为

O((N+Q)log⁡M),O((N+Q)\log M),

空间复杂度为 O(N+Q+M)O(N+Q+M)。

代码#

#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define sp << ' ' <<
#define inf 0x3f3f3f3f3f3f3f3f
#define N 100005
#define M 1000005
#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) (x & -x)
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
auto solve = [&]() {
ll n, m, q;
cin >> n >> m >> q;
vector<ll> tr1(m + 5, 0);
vector<ll> tr2(m + 5, 0);
vector<pr> block(n + 5);
for (int i = 1; i <= n; i++) {
cin >> block[i].first >> block[i].second;
}
vector<vector<tuple<ll, ll, ll>>> enter(n + 5); //
vector<vector<tuple<ll, ll, ll>>> settle(n + 5);
for (int i = 1; i <= q; i++) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
enter[a].push_back({i, c, d});
settle[b].push_back({i, c, d});
}
auto add = [&](vector<ll> &tr, ll x, ll add) {
for (; x <= m; x += lowbit(x))
tr[x] += add;
};
auto query = [&](vector<ll> &tr, ll x) {
ll res = 0;
for (; x; x -= lowbit(x))
res += tr[x];
return res;
};
auto modify = [&](ll l, ll r, ll k) {
add(tr1, l, k);
add(tr1, r + 1, -k);
add(tr2, l, k * (l - 1));
add(tr2, r + 1, -k * r);
};
auto query_interval = [&](ll l, ll r) {
return (query(tr1, r) * r - query(tr2, r) - (query(tr1, l - 1) * (l - 1) - query(tr2, l - 1)));
};
vector<ll> ans(q + 5, 0);
for (int i = 1; i <= n; i++) {
for (auto [id, l, r] : enter[i]) {
ans[id] -= query_interval(l, r);
}
modify(block[i].first, block[i].second, 1);
for (auto [id, l, r] : settle[i]) {
ans[id] += query_interval(l, r);
}
}
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
};
solve();
return 0;
}
AtCoder Beginner Contest 477 F:Count Cells in a Window
https://sanzenin.top/posts/obsidian/树状数组维护区间和/
作者
Sanzenin 凪
发布于
2026-10-04
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取