
AtCoder Beginner Contest 477 F:Count Cells in a Window
题目重述
给定一个 行 列的网格。第 行中,第 列到第 列的格子为黑色,其余格子为白色。
每次查询给出 ,求矩形区域
内黑色格子的数量。
约束为 ,且 。
关键观察
固定扫描到前 行,令 cover[x] 表示第 列在这些行中出现的黑格数量,则查询前缀行区间 对列区间 的答案就是
加入第 行时,需要对整个区间 加 ;查询时需要求列区间和。因此问题转化为:
- 区间加:对 中每个位置加 ;
- 区间求和:求 的元素和。
单棵树状数组适合“单点修改、前缀和查询”,不能直接同时完成区间加和区间求和。使用两棵树状数组维护差分数组即可支持这两种操作。
解析
两棵树状数组维护区间加、区间和
设对差分数组在位置 加上 、在位置 加上 。令第一棵树状数组维护这些差分值,第二棵树状数组维护差分值乘以位置偏移后的结果:
记两棵树状数组在位置 的前缀和分别为 、,则原数组的前缀和为
所以区间和可以写成
代码中的 modify(l, r, k) 实现区间加,query_interval(l, r) 实现区间求和。
按行编号离线处理查询
设一个查询为 。扫描行编号 时:
- 在处理第 行之前,树状数组维护的是第 到第 行,因此记录一次负贡献;
- 加入第 行到第 行后,树状数组维护的是第 到第 行,因此记录一次正贡献。
两次前缀状态之差恰好只保留第 到第 行的贡献。代码使用 enter[A] 保存负贡献事件,使用 settle[B] 保存正贡献事件:
其中 表示前 行在列区间 中的黑格数。
正确性说明
在扫描到第 行后,树状数组中每一列的值等于前 行该列黑格的数量,因为每行只在自己的黑色区间 上加 。因此 query_interval(C, D) 等于前 行在列区间 内的黑格总数。
对于查询 ,负事件发生在加入第 行前,得到 ;正事件发生在加入第 行后,得到 。两者相减后,编号不在 内的行贡献完全抵消,剩余值正是目标矩形中的黑格数量。
每次区间修改或区间查询需要 时间,所有行和查询的总复杂度为
空间复杂度为 。
代码
#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;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 43 天
部分内容可能已过时