将二维数点问题转移为二维偏序问题来做，CDQ分治主席树也可以做，但是本人太菜，只会树状数组做法：
无需离散化写法：(注意询问数组开四倍，树状数组0没有意义+1)
#include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 5e5 + 10, INF = 0x3f3f3f3f; int n; PII a[N]; int tr[10000005]; int m; ll ans[N]; struct ques { int x, y, id, type; ques(int _x = 0, int _y = 0, int _id = 0, int _type = 0) { x = _x; y = _y; id = _id; type = _type; } bool operator<(const ques &t)const { if (x == t.x) { return y < t.y; } else { return x < t.x; } } } q[N << 2]; int cnt; inline int lowbit(int x) { return x & -x; } void modify(int x, int t) { for (int i = x; i < 10000005; i += lowbit(i)) { tr[i] += t; } } int query(int x) { ll sum = 0; for (int i = x; i; i -= lowbit(i)) { sum += tr[i]; } return sum; } void solve() { cnt = 0; n = read(); m = read(); for (int i = 1; i <= n; i++) { a[i].x = read() + 1; a[i].y = read() + 1; } for (int i = 1; i <= m; i++) { int x1, x2, y1, y2; x1 = read() + 1; y1 = read() + 1; x2 = read() + 1; y2 = read() + 1; q[++cnt] = ques(x2, y2, i, 1); q[++cnt] = ques(x2, y1 - 1, i, -1); q[++cnt] = ques(x1 - 1, y2, i, -1); q[++cnt] = ques(x1 - 1, y1 - 1, i, 1); } sort(a + 1, a + 1 + n); sort(q + 1, q + 1 + cnt); int now = 1; for (int i = 1; i <= cnt; i++) { while (a[now].x <= q[i].x && now <= n) { modify(a[now].y, 1); now++; } ans[q[i].id] += 1LL * q[i].type * query(q[i].y); } for (int i = 1; i <= m; i++) { write(ans[i]); puts(""); } } signed main() { //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin >> __; while (__--) { solve(); } return 0; }
需要离散化写法：
这时要将两个数组放到一起
不需要加一，离散化会配好的：
/********************************************************************* 程序名: 版权: 作者: Joecai 日期: 2022-05-12 14:44 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 1e6 + 10, INF = 0x3f3f3f3f; int n, m; int tr[N]; int t[N]; int ans[N]; inline int read() { int X = 0; bool flag = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') flag = 0; ch = getchar(); } while (ch >= '0' && ch <= '9') { X = (X << 1) + (X << 3) + ch - '0'; ch = getchar(); } if (flag) return X; return ~(X - 1); } inline void write(int X) { if (X < 0) { X = ~(X - 1); putchar('-'); } if (X > 9) write(X / 10); putchar(X % 10 + '0'); } struct node { int x; int y; int id; int type; node(int _x = 0, int _y = 0, int _id = 0, int _type = 0) { x = _x; y = _y; id = _id; type = _type; } bool operator<(const node &w)const { if (x == w.x) { if (y == w.y) { return id < w.id; } else return y < w.y; } else return x < w.x; } } q[N]; inline int lowbit(int x) { return x & (-x); } void up(int x, int s) { for (int i = x; i < N; i += lowbit(i)) { tr[i] += s; } } int query(int x) { int sum = 0; for (int i = x; i; i -= lowbit(i)) { sum += tr[i]; } return sum; } void solve() { int cnt = 0; memset(tr, 0, sizeof(tr)); memset(ans, 0, sizeof(ans)); cin >> n >> m; for (int i = 1; i <= n; i++) { int x; x = read(); q[++cnt].x = i; q[cnt].y = x; q[cnt].type = 0; q[cnt].id = 0; } for (int i = 1; i <= m; i++) { int x, y, z; x = read(); y = read(); z = read(); q[++cnt] = node(y, z, i, 1); q[++cnt] = node(x - 1, -1, i, 1); q[++cnt] = node(x - 1, z, i, -1); q[++cnt] = node(y, -1, i, -1); } for (int i = 1; i <= cnt; i++) t[i] = q[i].y; sort(q + 1, q + 1 + cnt); sort(t + 1, t + 1 + cnt); int te = unique(t + 1, t + 1 + cnt) - t - 1; for (int i = 1; i <= cnt; i++) { q[i].y = lower_bound(t + 1, t + 1 + te, q[i].y) - t; } for (int i = 1; i <= cnt; i++) { if (q[i].id) //查询的点 { ans[q[i].id] += q[i].type * query(q[i].y); } else { up(q[i].y, 1); } } for (int i = 1; i <= m; i++) { write(ans[i]); printf(" "); } cout << endl; } signed main() { //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; cin >> __; while (__--) { solve(); } return 0; }
/********************************************************************* 程序名: 版权: 作者: Joecai 日期: 2022-05-12 16:20 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 1e6 + 10, INF = 0x3f3f3f3f; int n; int tr[N]; inline int lowbit(int x) { return x & (-x); } void up(int x, int s) { for (int i = x; i < N; i += lowbit(i)) { tr[i] += s; } } int query(int x) { int sum = 0; for (int i = x; i; i -= lowbit(i)) { sum += tr[i]; } return sum; } struct node { int x; int y; int id; int type; node(int _x = 0, int _y = 0, int _id = 0, int _type = 0) { x = _x; y = _y; id = _id; type = _type; } bool operator<(const node &w)const { if (x == w.x) { return y < w.y; } else return x < w.x; } } q[N]; int t[N]; int ans[N]; void solve() { int n; cin >> n; int cnt = 0; for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; q[++cnt].x = x; q[cnt].y = y; q[++cnt] = node(y, y, i, 1); q[++cnt] = node(x - 1, x - 1, i, 1); q[++cnt] = node(x - 1, y, i, -1); q[++cnt] = node(y, x - 1, i, -1); } sort(q + 1, q + 1 + cnt); for (int i = 1; i <= cnt; i++) t[i] = q[i].y; sort(t + 1, t + 1 + cnt); int te = unique(t + 1, t + 1 + cnt) - t - 1; for (int i = 1; i <= cnt; i++) { q[i].y = lower_bound(t + 1, t + 1 + te, q[i].y) - t; } for (int i = 1; i <= cnt; i++) { if (q[i].id) { ans[q[i].id] += q[i].type * query(q[i].y); } else up(q[i].y, 1); } for (int i = 1; i <= n; i++) { cout << ans[i] - 1 << endl; } } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }
