题目链接

点击打开链接

题目概括

在一个二维平面上有$n$个点$x_i,y_i$。
给定$m$个询问

  • a b c d,询问矩形区域($(a,b)$为左下角,$(c,d)$为右上角),内有多少点。

思路要点

考虑离线后分治
首先按照套路将答案转化成前缀和容斥的形式
$$Ans=Sum(c,d)-Sum(a-1,d)-Sum(c,b-1)+Sum(a-1,b-1)$$
然后问题就变成了求解$(1,1,x,y)$的答案。
再次转化成偏序问题
$$x_j\leq x_i,y_j\leq y_i$$
考虑按照$x$排序后,用树状数组统计$y$的答案即可。
时间复杂度 $O(nlog_2n)$

代码

#include <bits/stdc++.h>

using namespace std;

template <class T> void chkmax(T& x, T y) {
  x = x > y ? x : y;
}

template <class T> void chkmin(T& x, T y) {
  x = x < y ? x : y;
}

template <class T> void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}

template <class T> void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}

template <class T> void writeln(T x) {
  write(x), puts("");
}

const int N = 5e5 + 5;

struct Fenwick {
  int a[N << 2], n; 
  
  void init(int x) {
    memset(a, 0, sizeof a);
    n = x; 
  }
  
  void modify(int pos, int val) {
    for (; pos <= n; pos += pos & -pos) {
      a[pos] += val;
    }
  }
  
  int query(int pos) {
    int res = 0; 
    for (; pos; pos -= pos & -pos) {
      res += a[pos];
    }
    return res;
  }
} bit;

struct Query {
  int x, y, type, id;
} qry[N * 5];

int n, m, qryCnt, cx, cy;
int x[N], dx[N], y[N], dy[N];
int ans[N];

void addEvent(int x, int y, int type, int id) {
  qry[++qryCnt] = (Query){x, y, type, id};
}

void solve(int l, int r) {
  if (l == r) {
    return;
  }
  int mid = (l + r) >> 1; 
  solve(l, mid), solve(mid + 1, r);
  for (int i = l; i <= mid; i++) {
    if (qry[i].type == 0) {
      bit.modify(qry[i].y, 1);
    }
  }
  for (int i = mid + 1; i <= r; i++) {
    if (qry[i].type != 0) {
      ans[qry[i].id] += qry[i].type * bit.query(qry[i].y);
    }
  }
  for (int i = l; i <= mid; i++) {
    if (qry[i].type == 0) {
      bit.modify(qry[i].y, -1);
    }
  }
}

int main() {
  read(n); read(m);
  cx = cy = qryCnt = 0;
  for (int i = 1; i <= n; i++) {
    int x, y; 
    read(x), read(y);
    addEvent(x, y, 0, 0);
  }
  for (int i = 1; i <= m; i++) {
    int a, b, c, d;
    read(a), read(b), read(c), read(d);
    addEvent(a - 1, b - 1, 1, i);
    addEvent(a - 1, d, -1, i);
    addEvent(c, b - 1, -1, i);
    addEvent(c, d, 1, i);
    dx[++cx] = a - 1;
    dx[++cx] = c; 
    dy[++cy] = b - 1; 
    dy[++cy] = d;
  }
  sort(dx + 1, dx + 1 + cx); 
  sort(dy + 1, dy + 1 + cy);
  cx = unique(dx + 1, dx + 1 + cx) - dx - 1;
  cy = unique(dy + 1, dy + 1 + cy) - dy - 1; 
  bit.init(cy);
  for (int i = 1; i <= qryCnt; i++) {
    qry[i].x = lower_bound(dx + 1, dx + 1 + cx, qry[i].x) - dx; 
    qry[i].y = lower_bound(dy + 1, dy + 1 + cy, qry[i].y) - dy;
  }
  sort(qry + 1, qry + 1 + qryCnt, [](Query a, Query b) {
    if (a.x == b.x) {
      if (a.y == b.y) {
        return abs(a.type) < abs(b.type);
      } else {
        return a.y < b.y;
      }
    } else {
      return a.x < b.x;
    }
  });
  solve(1, qryCnt);
  for (int i = 1; i <= m; i++) {
    writeln(ans[i]);
  }
  return 0; 
}
最后修改:2020 年 03 月 06 日 10 : 03 PM
如果觉得我的文章对你有用,请随意赞赏