2026 杭电春季联赛 2——1005-守矢晨风(扫描线维护的激活集合可以应用差分思想, 这样只需要维护一个前缀激活集合即可) · znzryb
## 题目大意
**题目描述**
给定平面上 $n$ 个圆形区域,第 $i$ 个圆的圆心坐标为 $(p_i, q_i)$,半径为 $r_i$(保证 $r_i \le 30$)。
给定 $m$ 次询问,每次询问给出一个四边平行于坐标轴的矩形区域,指定了其左下角顶点坐标 $(x_{i,1}, y_{i,1})$ 和右上角顶点坐标 $(x_{i,2}, y_{i,2})$。对于每次询问,需要计算出在给定的 $n$ 个圆中,有多少个圆与该矩形区域存在至少一个公共点。
**数据范围**
测试用例数量 $t$ 满足 $1 \le t \le 1000$。
每次测试中的圆的个数 $n$ 满足 $1 \le n \le 1.5 \times 10^6$,询问的个数 $m$ 满足 $1 \le m \le 10^4$。
对于全部测试用例,保证 $\sum n \le 3 \times 10^6$,$\sum m \le 2 \times 10^4$。
坐标与半径范围:$1 \le p_i, q_i \le 10^9$,$1 \le r_i \le 30$,$1 \le x_{i,1} \le x_{i,2} \le 10^9$,$1 \le y_{i,1} \le y_{i,2} \le 10^9$。
**样例输入**
```
2
4 1
1 1 1
7 1 2
5 3 2
1 2 1
2 2 6 4
8 3
5 6 4
7 7 4
3 3 2
1 8 5
10 1 2
1 8 1
7 2 2
5 4 5
9 1 10 5
3 1 6 3
5 1 9 5
```
**样例输出**
```
3
4
4
7
```
**样例解释**
在第一组测试数据中,共有 $4$ 个圆和 $1$ 次询问。询问给定的矩形左下角坐标为 $(2, 2)$,右上角坐标为 $(6, 4)$。经过判断,该矩形与输入的第 $2$ 个圆、第 $3$ 个圆以及第 $4$ 个圆(总计三个圆形)存在公共点,因此该次询问的答案为 $3$。第二组测试数据同理,分别输出对应矩形内包含公共点的圆的数量。

## 思路讲解
这道题目应该是一道扫描线+树状数组,应该是不需要用到这个 K-D 树这种比较高级的东西的。
呃,那我们怎么做这道题目呢?首先就是用这个数据结构,快速求解出大矩形中的这个点,所谓的大矩形,就是矩形和圆的 minkowski 和(这个 minkowski 和是一个圆角矩形),当然,圆角矩形让我们用数据结构处理实在是,我们忽略其圆角,得到的就是所谓的“大矩形”(即图中黑色框框住的部分)。
[小羊-2025-12-04-M. Ahmad's Dish(圆和正多边形的这个 minkowski 和)(minkowski 和的交换不变性)](/2026/02/04/20260204-6657fe08)

[2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork(判断砖块是否重叠)(扫描线的本质就是遍历一个出一个)(维护一个当前生效的集合)(把二维的问题变为一维的问题来做)](/2026/02/06/20260206-95397573)
okay,我们上面的这个对扫描线总结的比较好。扫描线的重点就是维护一个当前生效的这个集合。按照一顺序排序后,那么我们其实**就是要维护一个目前生效的圆的集合**。
首先呢,就是这道题目,**因为半径比较少**,我们不妨**把这个不同半径的圆分开处理**。
然后因为我们目前把不同的半径分开处理,我们目前可以假设,所有的圆的这个半径都是相同的。我们就是像上面一样,把这个矩形扩大这个半径(👆想上面那个黑色的矩形一样)。
~~然后我们把矩形先按照 x 的右端点排序,再按照 x 的左端点排序~~。不过,我们发现,无论你怎么排序这个矩形和这个点(也就是这个圆心嘛),都很难维护一个严格生效的这个点的集合,主要也是矩形的是一个这个区间范围,无论怎么排都比较麻烦。
不过我们采用差分思想?其实就是如下方法:
**左查询**:在 $X = X_{min} - 1$ 的时刻,查询树状数组中 $[Y_{min}, Y_{max}]$ 区间的点数,记为 $A$,从答案中**减去** $A$。(记录权重为 $-1$)
**右查询**:在 $X = X_{max}$ 的时刻,查询树状数组中 $[Y_{min}, Y_{max}]$ 区间的点数,记为 $B$,加到答案中。(记录权重为 $+1$)
采用如上👆方法,我们只需要维护一个 $[-INF,idx]$ 的生效点集合就可以了,可以说是非常轻松惬意了,我们也不需要删除。
然后我们要进行这个几何点的这个扣除:

只要像上面👆一样,不断的枚举这个 dx,就可以排除掉所有的这个不合法的点。
```cpp
struct Solve {
ll N, M;
Compress_<ll> li_y;
vector<vector<X_y> > r_xy_ls;
vector<Event> events_backup;
vector<int> Ans;
vector<Event> gen_event(ll r) {
// vector<Event> tmp_events;
vector<Event> events;
// tmp_events.reserve(SZ(r_xy_ls[r]));
for (auto [x,y]: r_xy_ls[r]) {
events.push_back({x, y, Insert});
}
for (auto e: events_backup) {
e.y1 -= r;
e.y2 += r;
if (e.type == Left) {
e.x -= r;
} else if (e.type == Right) {
e.x += r;
}
events.push_back(e);
}
sort(all(events));
return events;
}
void solve_single_r(ll r) {
BIT tr(li_y.size());
sort(all(r_xy_ls[r]));
auto events = gen_event(r);
for (auto &e: events) {
if (e.type == Insert) {
tr.add(li_y.get_i(e.y1), 1);
} else if (e.type == Left) {
Ans[e.id] -= tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y1+r,-1,-1);
Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y2-r,-1,1);
} else {
Ans[e.id] += tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y1+r,1,-1);
Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y2-r,1,1);
}
}
}
// 查找以这个 x 为首的,在范围 [ly,ry] 之间的这个点的数量
ll query_r_x_l_r_cnt(ll r, ll x, ll ly, ll ry) {
if (ly > ry) {
return 0;
}
auto &xy_ls = r_xy_ls[r];
auto itl = lower_bound(all(xy_ls), X_y{x, ly});
if (itl == xy_ls.end()) {
return 0;
}
if (itl->x != x) {
return 0;
}
if (itl->y > ry) {
return 0;
}
auto itr = upper_bound(all(xy_ls), X_y{x, ry});
ll num = itr - itl;
return num;
}
// 计算边缘的,可能被多算的这个点。
ll redundant_circle_cnt(ll r, ll x, ll y, ll dirx, ll diry) {
ll res = 0;
for (int dx = 1; dx <= r; ++dx) {
ll tox = x + dirx * dx;
ll disy = sqrtl(r * r - dx * dx);
ll toy = y + diry * disy;
ll ly = min(toy + diry, y + diry * r);
ll ry=max(toy + diry, y + diry * r);
res += query_r_x_l_r_cnt(r, tox, ly, ry);
}
return res;
}
Solve() : r_xy_ls(32) {
cin >> N >> M;
li_y.reserve(N + M);
// for (int i = 1; i <= 30; ++i) r_xy_ls[i].reserve(N);
for (int i = 1; i <= N; ++i) {
ll x, y, d;
cin >> x >> y >> d;
r_xy_ls[d].push_back({x, y});
li_y.add(y);
}
events_backup.reserve(N + 30 * M);
Ans.resize(M);
for (int i = 0; i < M; ++i) {
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int r = 0; r <= 30; ++r) {
li_y.add(y1 - r, y2 + r);
}
events_backup.push_back({x1, y1, Left, i, y2});
events_backup.push_back({x2, y1, Right, i, y2});
}
sort(all(events_backup));
li_y.init();
for (int i = 1; i <= 30; ++i) {
solve_single_r(i);
}
for (int i = 0; i < M; ++i) {
cout << Ans[i] << "\n";
}
}
};
```
## AC代码
AC
[https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19570](https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19570)
::: 源代码
```cpp
// teamname: Gospel_rock
/**
* Problem: 守矢晨风
* Contest:
* Judge: HDOJ
* URL: https://acm.hdu.edu.cn/contest/problem?cid=1198&pid=1005
* Created: 2026-04-02 10:51:46
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
/* 参考了 https://github.com/hh2048/XCPC/blob/484e9e0e6e4f127f187eb3df5bc419e9ec863795/02%20-%20%E6%89%93%E5%8D%B0%E7%A8%BF%E6%A8%A1%E6%9D%BF%E6%B1%87%E6%80%BB/08%20-%20%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.md#L737
*
*/
template<typename T>
struct Compress_ {
// shift=0 就是采用 0-based 下标
// shift=1 就是采用 1-based 下标
int n, shift = 1;
vector<T> alls;
Compress_() {
}
// 预估大小
Compress_(ll n_) {
alls.reserve(n_);
}
Compress_(vector<T> in) : alls(in) {
init();
}
void add(T x) {
alls.emplace_back(x);
}
template<typename... Args>
void add(T x, Args... args) {
add(x), add(args...);
}
void reserve(ll n_) {
alls.reserve(n_);
}
void init() {
alls.emplace_back(numeric_limits<T>::max());
sort(alls.begin(), alls.end());
alls.resize(unique(alls.begin(), alls.end()) - alls.begin());
this->n = alls.size();
}
int size() {
return n;
}
int get_i(T x) {
// 返回 x 元素的新下标
return upper_bound(alls.begin(), alls.end(), x) - alls.begin() + shift;
}
T operator[](int idx) {
// 根据新下标返回原来元素
assert(idx - shift < n);
return idx - shift < n ? alls[idx - shift] : -1;
}
bool contains(T x) {
// 查找元素 x 是否存在
return binary_search(alls.begin(), alls.end(), x);
}
friend auto &operator<<(ostream &o, const auto &j) {
cout << "{";
for (auto it: j.alls) {
o << it << " ";
}
return o << "}";
}
};
// by znzryb
// 普通的单点修改区间查询树状数组,含有查找第K个空位,第K个元素的功能
// https://www.codechef.com/viewsolution/1179893708 查找第K个元素测试
// 第K个空位的测试应该是一道abc的题目,但是当时没保存
struct BIT {
vector<ll> tr;
int n;
inline int lowbit(int x) {
return x & (-x);
}
BIT(int ln) {
// 构造+初始化函数
n = ln;
tr.resize(n + 5, 0);
}
BIT() {
}
inline void add(int p, ll x) {
if (p == 0) return;
while (p <= n) {
tr[p] += x;
p += lowbit(p);
}
}
inline ll query(int l, int r) {
ll lres = 0, rres = 0;
l -= 1;
while (l > 0) {
lres += tr[l];
l -= lowbit(l);
}
while (r > 0) {
rres += tr[r];
r -= lowbit(r);
}
return rres - lres;
}
inline int findkth(int k) {
// 找到第k个元素,当然应当是要求只能出现0和1
int x = 0, sum = 0;
for (int i = __lg(n); ~i; --i) {
x += 1 << i;
if (x >= n || sum + tr[x] >= k) {
x -= 1 << i;
} else {
sum += tr[x];
}
}
return x + 1; // 我们始终让cx < k,所以返回的就是最大的比k小的,+1就是新元素出现的地方
}
inline int kthspace(int k) {
// 找到第k个空位,当然应当是要求只能出现0和1
int cx = 0;
for (int i = 1 << 20; i > 0; i >>= 1) {
// 这个你可以理解为不断缩小步长的搜索
if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
// lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
k -= lowbit(cx + i) - tr[cx + i];
cx += i;
}
}
return cx + 1; // 我们始终让cx < k,所以返回的就是最大的比k小的,+1就是新空位出现的地方
}
};
struct X_y {
ll x;
ll y;
bool operator<(const X_y &o) const {
if (x != o.x) return x < o.x;
return y < o.y;
}
bool operator==(const X_y &o) const {
return x == o.x && y == o.y;
}
};
enum my_enum {
Left,
Insert,
Right,
};
struct Event {
ll x, y1;
my_enum type;
int id;
ll y2;
bool operator<(const Event &o) const {
if (x != o.x) return x < o.x;
if (type != o.type) return type < o.type;
return y1 < o.y1;
}
};
struct Solve {
ll N, M;
Compress_<ll> li_y;
vector<vector<X_y> > r_xy_ls;
vector<Event> events_backup;
vector<int> Ans;
vector<Event> gen_event(ll r) {
// vector<Event> tmp_events;
vector<Event> events;
// tmp_events.reserve(SZ(r_xy_ls[r]));
for (auto [x,y]: r_xy_ls[r]) {
events.push_back({x, y, Insert});
}
for (auto e: events_backup) {
e.y1 -= r;
e.y2 += r;
if (e.type == Left) {
e.x -= r;
} else if (e.type == Right) {
e.x += r;
}
events.push_back(e);
}
sort(all(events));
return events;
}
// 这边的这个计算是不管这个边缘的,可能被多算的点的
void solve_single_r(ll r) {
BIT tr(li_y.size());
sort(all(r_xy_ls[r]));
auto events = gen_event(r);
for (auto &e: events) {
if (e.type == Insert) {
tr.add(li_y.get_i(e.y1), 1);
} else if (e.type == Left) {
Ans[e.id] -= tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y1+r,-1,-1);
Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y2-r,-1,1);
} else {
Ans[e.id] += tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y1+r,1,-1);
Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y2-r,1,1);
}
}
}
ll query_r_x_l_r_cnt(ll r, ll x, ll ly, ll ry) {
if (ly > ry) {
return 0;
}
auto &xy_ls = r_xy_ls[r];
auto itl = lower_bound(all(xy_ls), X_y{x, ly});
if (itl == xy_ls.end()) {
return 0;
}
if (itl->x != x) {
return 0;
}
if (itl->y > ry) {
return 0;
}
auto itr = upper_bound(all(xy_ls), X_y{x, ry});
ll num = itr - itl;
return num;
}
ll redundant_circle_cnt(ll r, ll x, ll y, ll dirx, ll diry) {
ll res = 0;
for (int dx = 1; dx <= r; ++dx) {
ll tox = x + dirx * dx;
ll disy = sqrtl(r * r - dx * dx);
ll toy = y + diry * disy;
ll ly = min(toy + diry, y + diry * r);
ll ry=max(toy + diry, y + diry * r);
res += query_r_x_l_r_cnt(r, tox, ly, ry);
}
return res;
}
Solve() : r_xy_ls(32) {
cin >> N >> M;
li_y.reserve(N + M);
// for (int i = 1; i <= 30; ++i) r_xy_ls[i].reserve(N);
for (int i = 1; i <= N; ++i) {
ll x, y, d;
cin >> x >> y >> d;
r_xy_ls[d].push_back({x, y});
li_y.add(y);
}
events_backup.reserve(N + 30 * M);
Ans.resize(M);
for (int i = 0; i < M; ++i) {
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int r = 0; r <= 30; ++r) {
li_y.add(y1 - r, y2 + r);
}
events_backup.push_back({x1, y1, Left, i, y2});
events_backup.push_back({x2, y1, Right, i, y2});
}
sort(all(events_backup));
li_y.init();
for (int i = 1; i <= 30; ++i) {
solve_single_r(i);
}
for (int i = 0; i < M; ++i) {
cout << Ans[i] << "\n";
}
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve solve;
return 0;
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19570
*/
```
:::
## 心路历程(WA,TLE,MLE……)
也是成功一次 AC 了,当然,在写一些模块的时候,ai 也帮助我进行了一些东西。