P2163 [SHOI2007] 园丁的烦恼
Tag：二维数点、离散化、树状数组
题目描述
第一行有两个整数 \(n, m\)，分别表示树木个数和询问次数。
接下来 \(n\) 行，每行两个整数 \(x, y\)，表示存在一棵坐标为 \((x, y)\) 的树。有可能存在两棵树位于同一坐标。
接下来 \(m\) 行，每行四个整数 \(a, b, c, d\)，表示查询以 \((a, b)\) 为左下角，\((c, d)\) 为右上角的矩形内部（包括边界）有多少棵树。
数据说明：
\(0 \leq n \leq 5 \times 10^5\)，\(1 \leq m \leq 5 \times 10^5\)，\(0 \leq x, y, a, b, c, d \leq 10^7\)，\(a \leq c\)，\(b \leq d\)
分析
题目主要需要实现的是在一个二维平面内求一个子矩形内有多少个点。 我们首先把题目画成图方便我们直观理解：
如果我们想要查询 \((a,b)\) 到 \((c,d)\) 这个子矩形内有多少点的话， 记 \(cnt_{x,y}\) 表示 左下角为 \((0,0)\) 为左下角，\((x,y)\) 为右上角的子矩形内有多少个点。 那么我们要求的答案实际上可以使用 \(cnt_{c,d} - cnt_{a-1,d} - cnt_{c,b-1} + cnt_{a-1,b-1}\) 来求出， 这实际上是一个二维前缀和。
结合本题并没有强制在线， 这启示我们可以把每一个查询拆成四个部分， 离线下来求解。
由于这个问题是二维的，我们可以想到对 \(x\) 进行排序之后， 只需要考虑 \(y\) 这一维。 把拆开的查询也排序之后， 问题就可以变成我们在查询上维护一个指针， 每次遍历到一个询问，就把这个询问的 \(y\) 小的所有点都想办法记录下来， 全记录下来之后，我们询问实际上要做的就是查询已经记录的点又有多少比当前查询的 \(x\) 要小的点。
上述的过程所提到的「记录」以及「查询」可以使用 \(\text{Fenwick}\) 来实现。
用 \(\text{Fenwick}\) 求解的话还有一个问题， 就是本题的值域较大，直接开一个和值域一样大的 \(\text{Fenwick}\) 是不实际的。 所以我们需要对所有的 \(y\) 进行一次离散化。
代码实现
struct Fenwick {
// static const int fenwickMax = 1e6 + 5;
// int tree[fenwickMax];
int n;
vector<int> tree;
int lowBit(int x) { return -x & x; }
void init(int x) {
n = x;
tree.assign(x + 1,0);
}
void add(int x, int k) {
while (x <= n) {
tree[x] += k;
x += lowBit(x);
}
}
int query(int x) {
int ans = 0;
while (x) {
ans += tree[x];
x -= lowBit(x);
}
return ans;
}
};
Fenwick fenwick;
void solve() {
struct point {
int x, y;
};
struct query {
int pos, x, id, tag;
};
int n, m;
cin >> n >> m;
vector<point> vec(n + 1);
vector<int> all;
for (int i = 1; i <= n; ++i) {
auto &[x, y] = vec[i];
cin >> x >> y;
all.push_back(y);
}
std::sort(vec.begin() + 1, vec.end(), [](point &x, point &y) {
return x.x < y.x;
});
vector<query> q;
for (int i = 1; i <= m; ++i) {
int l, a, r, b;
cin >> l >> a >> r >> b;
q.push_back({l - 1, a - 1, i, 1});
q.push_back({r, b, i, 1});
q.push_back({l - 1, b, i, -1});
q.push_back({r, a - 1, i, -1});
all.push_back(a - 1);
all.push_back(b);
}
std::sort(q.begin(), q.end(), [](query &a, query &b) {
return a.pos < b.pos;
});
vector<int> ans(m + 1);
std::sort(all.begin(), all.end());
all.resize(std::unique(all.begin(), all.end()) - all.begin());
fenwick.init(all.size());
auto rk = [&](int x) {
return std::lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
};
int idx = 1;
for (auto &[pos, x, id, tag]: q) {
while (idx <= n && vec[idx].x <= pos) {
fenwick.add(rk(vec[idx++].y), 1);
}
ans[id] += tag * fenwick.query(rk(x));
}
for (int i = 1; i <= m; ++i) {
cout << ans[i] << endl;
}
}
日志
本页面创建于 2024/09/16 16:14