题目大意：给定若干个点，询问任一矩阵中点的个数，数据规模，0≤n≤500000，1≤m≤500000，第i棵树的坐标（0≤xi，yi≤10000000）。
解法：和星那道题想法类似，对于二维的点，先按横坐标的大小排序，这样只剩下一维，然后再讨论y值，维护以原点为左下角，自己为右上角的点的个数，用树状数组维护，然后将询问编号（即离线处理），按y值排序依次处理，最后按照类似二维前缀和的方式求得每一个询问的答案即可。
#include <bits/stdc++.h> using namespace std; struct node { int x, y, id; bool operator< (node q) const { return x - q.x ? x < q.x : y - q.y ? y < q.y : id < q.id; } }a[20000005]; int q[20000005], dx[20000005], ans[10000005][5], c[20000005], n, m, tot; void modify(int x, int p) {while (x <= n) c[x] += p, x += (x & -x);} int query(int x) {int ans = 0; while (x) ans += c[x], x -= (x & -x); return ans;} int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i].x, &a[i].y); a[i].id = 0; } for (int i = 1, xx, yy, xxx, yyy; i <= m; i++) { scanf("%d%d%d%d", &xx, &yy, &xxx, &yyy), xx--, yy--; a[++n].x = xx, a[n].y = yy, a[n].id = i; a[++n].x = xxx, a[n].y = yyy, a[n].id = i; a[++n].x = xxx, a[n].y = yy, a[n].id = i; a[++n].x = xx, a[n].y = yyy, a[n].id = i; } sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) q[i] = a[i].y; sort(q + 1, q + n + 1); tot = unique(q + 1, q + n + 1) - q - 1; for (int i = 1; i <= n; i++) { if (a[i].id) { ans[a[i].id][++dx[a[i].id]] = query(lower_bound(q + 1, q + tot + 1, a[i].y) - q); } else { modify(lower_bound(q + 1, q + tot + 1, a[i].y) - q, 1); } } for (int i = 1; i <= m; i++) { printf("%d\n", ans[i][1] - ans[i][2] - ans[i][3] + ans[i][4]); } }