静态询问平面点数

\(x_i,\ y_i\in[0,\ 10^7],\ n,\ m\leq5\times10^5\)

二维偏序，cdq分治

---

可以直接 cdq分治，也可以离散化后用 BIT 做、、注意排序时若 \(x,\ y\) 相同，要将点放在询问前面

时间复杂度 \(O(n\log n)\)

代码

cdq分治

#include 
    
     using namespace std;#define nc getchar()const int maxn = 5e5 + 10;int n, m, len, ans[maxn];struct node {  int x, y, val, tid;  node(int _x = 0, int _y = 0, int _v = 0, int _t = 0) :    x(_x), y(_y), val(_v), tid(_t) {}  bool operator < (const node& o) const {    return x == o.x ? y == o.y ? !val : y < o.y : x < o.x;  }} a[maxn * 5], b[maxn * 5];inline int read() {  int x = 0;  char c = nc;  while (c < 48) c = nc;  while (c > 47) x = x * 10 + c - 48, c = nc;  return x;}void cdq(int l, int r) {  if (l == r) return;  int mid = (l + r) >> 1;  cdq(l, mid), cdq(mid + 1, r);  for (int p = l, p1 = l, p2 = mid + 1, s = 0; p <= r; p++) {    if (p2 > r || (p1 <= mid && a[p1].y <= a[p2].y)) {      s += !a[p1].val, b[p] = a[p1++];    } else {      ans[a[p2].tid] += a[p2].val * s, b[p] = a[p2++];    }  }  for (int i = l; i <= r; i++) {    a[i] = b[i];  }}int main() {  n = read(), m = read();  for (int i = 1; i <= n; i++) {    a[i].x = read(), a[i].y = read();  }  len = n;  for (int i = 1; i <= m; i++) {    int x1 = read(), y1 = read();    int x2 = read(), y2 = read();    a[++len] = node(x2, y2, 1, i);    a[++len] = node(x1 - 1, y2, -1, i);    a[++len] = node(x2, y1 - 1, -1, i);    a[++len] = node(x1 - 1, y1 - 1, 1, i);  }  sort(a + 1, a + len + 1), cdq(1, len);  for (int i = 1; i <= m; i++) {    printf("%d\n", ans[i]);  }  return 0;}
    

BIT

#include 
    
     using namespace std;#define nc getchar()#define get_val(x) (lower_bound(data + 1, data + tot + 1, x) - data)const int maxn = 5e5 + 10;int n, m, len, tot, ans[maxn], data[maxn * 5], c[maxn * 5];struct Query {  int x, y, val, tid;  Query(int _x = 0, int _y = 0, int _v = 0, int _t = 0) :    x(_x), y(_y), val(_v), tid(_t) {}  inline bool operator < (const Query& o) const {    return x == o.x ? y == o.y ? !val : y < o.y : x < o.x;  }} Q[maxn * 5];inline int read() {  int x = 0;  char c = nc;  while (c < 48) c = nc;  while (c > 47) x = (x << 3) + (x << 1) + (c ^ 48), c = nc;  return x;}inline void add(int pos) {  for (; pos <= tot; pos += pos & -pos) {    c[pos]++;  }}inline int query(int pos) {  int res = 0;  for (; pos; pos &= pos - 1) {    res += c[pos];  }  return res;}int main() {  n = read(), m = read();  for (int i = 1; i <= n; i++) {    data[++tot] = Q[i].x = read();    data[++tot] = Q[i].y = read();  }  len = n;  for (int i = 1; i <= m; i++) {    int x1 = read(), y1 = read();    int x2 = read(), y2 = read();    if (x1) data[++tot] = x1 - 1;    if (y1) data[++tot] = y1 - 1;    data[++tot] = x2, data[++tot] = y2;    Q[++len] = Query(x2, y2, 1, i);    if (x1) Q[++len] = Query(x1 - 1, y2, -1, i);    if (y1) Q[++len] = Query(x2, y1 - 1, -1, i);    if (x1 && y1) Q[++len] = Query(x1 - 1, y1 - 1, 1, i);  }  sort(data + 1, data + tot + 1);  tot = unique(data + 1, data + tot + 1) - data - 1;  for (int i = 1; i <= len; i++) {    Q[i].x = get_val(Q[i].x);    Q[i].y = get_val(Q[i].y);  }  sort(Q + 1, Q + len + 1);  for (int i = 1; i <= len; i++) {    if (Q[i].val) {      ans[Q[i].tid] += Q[i].val * query(Q[i].y);    } else {      add(Q[i].y);    }  }  for (int i = 1; i <= m; i++) {    printf("%d\n", ans[i]);  }  return 0;}