这题如果用二维树状数组，则会直接爆内存。
那么可以运用扫描线的思路。
就是，它同时被x和y限制了，那么可以在查询的时候，确保x先满足了，（把x按小到大排序）
然后就相当于是关于y的一个一维bit了，
注意同一个点它询问两次。
8
2 2
1 1
1 2
1 3
1 4
1 5
2 1
0 1
2
1 1
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e6 + 22; struct node { int x, y, id; bool operator < (const struct node & rhs) const { if (x != rhs.x) return x < rhs.x; else return y < rhs.y; } }a[maxn]; int c[maxn]; int lowbit(int x) { return x & (-x); } void upDate(int pos, int val) { while (pos <= maxn - 2) { c[pos] += val; pos += lowbit(pos); } } int sum(int pos) { int ans = 0; while (pos > 0) { ans += c[pos]; pos -= lowbit(pos); } return ans; } int ser[maxn]; int ans[maxn]; int n; vector<int>want; void work() { memset(c, 0, sizeof c); // scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d", &a[i].x, &a[i].y); a[i].x++; a[i].y++; a[i].id = i; } sort(a + 1, a + 1 + n); // for (int i = 1; i <= n; ++i) { // printf("%d %d %d ", a[i].x, a[i].y, a[i].id); // } int m; scanf("%d", &m); memset(ser, 0, sizeof ser); for (int i = 1; i <= m; ++i) { int id; scanf("%d", &id); ser[id] = i; want.push_back(id); } for (int i = 1; i <= n; ++i) { if (ser[a[i].id]) { ans[a[i].id] = sum(a[i].y); } upDate(a[i].y, 1); } for (int i = 0; i < want.size(); ++i) { printf("%d ", ans[want[i]]); } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d", &n) != EOF) work(); return 0; }