AOJ2426 Treasure Hunt

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426

N個の宝の座標が与えられる。座標には重複も含む。
M個のクエリが与えられる。各クエリは長方形領域を示す。
クエリに対し、領域に含まれる宝の数を答えよ。
長方形領域は境界を含む。点や線分であることもある。

解説
宝の座標のみを用いて座標圧縮をする。こうすると、平面が高々5000*5000に収まる。
よって、各圧縮後の座標において宝の数を数えることが出来る。
二次元累積和を取ることで、クエリの長方形領域にある宝の個数がO(1)で求まる。
和を取る境界関しての処理に注意が必要。[要追記]

int xs[5001], ys[5001];
int sum[5100][5100];
 
int main() {
 
  int N, M; cin >> N >> M;
  vector<int> X = {-inf, inf}, Y = {-inf, inf};
  rep(i, N) {
    scanf("%d%d", &xs[i], &ys[i]);
    X.push_back(xs[i]); Y.push_back(ys[i]);
  }
 
  sort(X.begin(), X.end()); X.erase(unique(all(X)), X.end());
  sort(Y.begin(), Y.end()); Y.erase(unique(all(Y)), Y.end());
 
  rep(i, N) {
    sum[upper_bound(all(Y), ys[i]) - Y.begin()][upper_bound(all(X), xs[i]) - X.begin()] ++;
  }
 
  rep(i, Y.size() + 10) rep(j, X.size() + 10) {
    if(i && j) sum[i][j] -= sum[i-1][j-1];
    if(i) sum[i][j] += sum[i-1][j];
    if(j) sum[i][j] += sum[i][j-1];
  }
 
  rep(i, M) {
    int rx1, ry1, rx2, ry2; scanf("%d%d%d%d", &rx1, &ry1, &rx2, &ry2);
    int x1 = lower_bound(all(X), rx1) - X.begin();
    int y1 = lower_bound(all(Y), ry1) - Y.begin();
    int x2 = upper_bound(all(X), rx2) - X.begin();
    int y2 = upper_bound(all(Y), ry2) - Y.begin();
    printf("%d\n", sum[y2][x2] - sum[y2][x1] - sum[y1][x2] + sum[y1][x1]);
  }
 
  return 0;
}