二维数点问题
整体思路
\(~ ~ ~ ~ ~ ~ ~\)将所有点按x值从小到大排序，那么查询满足特定条件的点的时候，可以转化为只对y值查询，由此，只需要遍历横坐标，并在遍历过程中用树状数组的数据结构维护对y的操作即可
P2163 [SHOI2007] 园丁的烦恼
\(~ ~ ~ ~ ~ ~ ~\)题目链接：园丁的烦恼
题意
\(~ ~ ~ ~ ~ ~ ~\)给n个点，m次询问，每次询问给出一个矩形，对于每次询问回答每个矩形里包含多少个点。不要求在线, \(0≤n≤5×10^5, 1≤m≤5×10^5, 0≤x,y,a,b,c,d≤10^7, a≤c, b≤d\)。
思路
\(~ ~ ~ ~ ~ ~ ~\)由于是离线的，可以把每个矩形看成从\((0,0)\)开始的四个矩形部分内点的数量加减得到的，即：
\[N_{total} = N_{x_2,y_2}-N_{x_1-1,y_2}-N_{x_2,y_1-1}+N_{x_1-1,y_1-1}
\]
\(~ ~ ~ ~ ~ ~ ~\)这样我们可以把矩形对应的四个点全部放到一个数组里，对其按从小到大排序即可（重载运算符，按横坐标从小到大，纵坐标从下到大排序）。
\(~ ~ ~ ~ ~ ~ ~\)依次遍历排完序后每个矩阵的点，依次向树状数组种加入“小于”当前点的坐标，查询所有“小于”当前点的点的y值，累加到对应的第id次查询的答案中即可。
\(~ ~ ~ ~ ~ ~ ~\)注意：由于树状数组的输入和查询是从1到x，而本题中的x和y是从0开始，因此需要把坐标都先加一。
代码
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#define LL long long
using namespace std;
const int maxn = 5e5 + 5;
struct poi {
int x, y;
bool operator<(const poi b) const {
return x < b.x || (x == b.x && y < b.y);
}
bool operator==(const poi b) const { return x == b.x && y == b.y; }
} a[maxn];
struct matrix {
poi x;
int k, id;
bool operator<(const matrix b) const { return x < b.x; }
} q[4 * maxn];
int lowbit(int x) { return x & -x; }
int y[maxn], n, m, ans[maxn];
void add(int x, int d) {
while (x <= n) {
y[x] += d;
x += lowbit(x);
}
}
LL query(int x) {
LL sum = 0;
while (x > 0) {
sum += y[x];
x -= lowbit(x);
}
return sum;
}
void sol() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
for (int i = 1; i <= n; ++i) a[i].x++, a[i].y++;
sort(a + 1, a + n + 1);
for (int i = 1; i <= m; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
q[4 * i - 3] = matrix{x1, y1, 1, i};
q[4 * i - 2] = matrix{x2 + 1, y2 + 1, 1, i};
q[4 * i - 1] = matrix{x1, y2 + 1, -1, i};
q[4 * i] = matrix{x2 + 1, y1, -1, i};
}
m *= 4;
sort(q + 1, q + m + 1);
int idx = 1;
for (int i = 1; i <= m; ++i) {
while (idx <= n && (a[idx] < q[i].x || a[idx] == q[i].x)) {
add(a[idx].y, 1);
idx++;
}
// cout << q[i].k * query(q[i].x.y) << endl;
ans[q[i].id] += q[i].k * query(q[i].x.y);
}
for (int i = 1; i <= m / 4; ++i) cout << ans[i] << endl;
}
int main() {
sol();
return 0;
}