領域木(kd木) (from AOJ DSL_2-C : Range Query - Range Search (kD Tree))

DSL_2_C.py

# TLE(http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1843450)
# もうちょっと高速化したい
import sys
readline = sys.stdin.readline
from bisect import bisect, bisect_right
from itertools import chain
n = input()
n0 = 2**n.bit_length()
data = [None]*(n0*2)
# セグメント木の構築
def init(k, l, r):
    if r - l == 1:
        data[k] = [ys[l]]
    else:
        le = 2*k+1; ri = 2*k+2
        init(le, l, (l+r)/2)
        init(ri, (l+r)/2, r)
 
        # 一個下の要素をmergeする
        # (heapq.mergeがあるけど、list化すると遅くなる)
        # --> list(heapq.merge(data[le], data[ri]))
        data[k] = sorted(chain(data[le], data[ri]))
# [a, b)において、x以下の要素を取得
def query(a, b, x, k, l, r):
    if b<=l or r<=a:
        return []
    if a<=l and r<=b:
        d = data[k]
        idx = bisect_right(d, x)
        return d[:idx]
    lc = query(a, b, x, 2*k+1, l, (l+r)/2)
    rc = query(a, b, x, 2*k+2, (l+r)/2, r)
    return lc + rc
def solve(a, b, x):
    return query(a, b, x, 0, 0, n)
 
ps = [map(int, (readline() + " %d"%i).split()) for i in xrange(n)]
ps.sort()
xs = [x for x, y, i in ps]
ys = [(y, i) for x, y, i in ps]
 
init(0, 0, n)
 
q = input()
for i in xrange(q):
    sx, tx, sy, ty = map(int, readline().split())
    # xで探索して、左端の要素(l_idx)と右端の要素(r_idx)を求める
    l_idx = bisect(xs, sx-1)
    r_idx = bisect_right(xs, tx)
    # xで絞った要素から、sy <= y <= tyとなる(x, y)を見つける
    T = set(i for y, i in solve(l_idx, r_idx, (ty, n)))
    S = set(i for y, i in solve(l_idx, r_idx, (sy-1, n)))
    ans = list(T-S)
    ans.sort()
    for e in ans:
        print e
    print

DSL_2_C.cpp

// MLE (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1872176#1)
// 蟻本ベース書き
// Nがでかいとinitの時点でvectorがメモリ取り過ぎて足りなくなるので厳しい
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define DEBREPE(obj) for(auto e : obj) cout << e << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 10000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
typedef pair<P, int> PI;
typedef pair<int, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define N 1000003

vector<P> data[N];
class kdTree {
  private:
    int n;

    void init(int k, int l, int r, P *d) {
      if(r-l == 1) {
        data[k].push_back(d[l]);
      } else {
        int lch = 2*k+1, rch = 2*k+2;
        init(lch, l, (l+r)/2, d);
        init(rch, (l+r)/2, r, d);
        data[k].resize(r-l);

        merge(
            data[lch].begin(), data[lch].end(),
            data[rch].begin(), data[rch].end(),
            data[k].begin()
            );
      }
    }
    int r_query(int a, int b, int x0, int x1, int k, int l, int r, set<int> *result) {
      if(b <= l || r <= a) {
        return 0;
      } else if(a <= l && r <= b) {
        vector<P>::iterator it0 = upper_bound(data[k].begin(), data[k].end(), P(x0, -1));
        vector<P>::iterator it1 = upper_bound(data[k].begin(), data[k].end(), P(x1, -1));
        int sz = it1 - it0;
        while(it0 != it1) {
          (*result).insert((*it0).second);
          ++it0;
        }
        return sz;
      } else {
        int lc = r_query(a, b, x0, x1, 2*k+1, l, (l+r)/2, result);
        int rc = r_query(a, b, x0, x1, 2*k+2, (l+r)/2, r, result);

        return lc + rc;
      }
    }
  public:
    kdTree(int n, P *d) {
      this->n = n;
      init(0, 0, n, d);
    }
    // [a, b) * [x0, x1)
    int query(int a, int b, int x0, int x1, set<int> *result) {
      return r_query(a, b, x0, x1, 0, 0, n, result);
    }
};

IP ps[N];
int xs[N];
P ys[N];

int main() {
  int n;
  cin >> n;
  rep(i, n) {
    int x, y;
    cin >> x >> y;
    ps[i] = IP(x, P(y, i));
  }
  sort(ps, ps+n);
  repr(i, n) {
    IP &p = ps[i];
    xs[i] = p.first;
    ys[i] = p.second;
  }
  kdTree kdt(n, ys);

  int q;
  cin >> q;
  while(q--) {
    int sx, tx, sy, ty;
    cin >> sx >> tx >> sy >> ty;
    int left = lower_bound(xs, xs+n, sx) - xs;
    int right = lower_bound(xs, xs+n, tx+1) - xs;
    set<int> ss;
    kdt.query(left, right, sy, ty+1, &ss);

    for(set<int>::iterator it = ss.begin(); it != ss.end(); ++it) {
      cout << *it << endl;
    }
    cout << endl;
  }
  return 0;
}

kdtree.cpp

// C++用の単純に個数返すやつ (蟻本ベース)
// データの型でtemplate化したかったけど、data[N]のサイズでセグフォくらったのでなし
#define N 500003

vector<int> data[N];
class kdTree {
  private:
    int n;

    void init(int k, int l, int r, int *d) {
      if(r-l == 1) {
        data[k].push_back(d[l]);
      } else {
        int lch = 2*k+1, rch = 2*k+2;
        init(lch, l, (l+r)/2, d);
        init(rch, (l+r)/2, r, d);
        data[k].resize(r-l);

        merge(
            data[lch].begin(), data[lch].end(),
            data[rch].begin(), data[rch].end(),
            data[k].begin()
            );
      }
    }
    int r_query(int a, int b, int x, int k, int l, int r) {
      if(b <= l || r <= a) {
        return 0;
      } else if(a <= l && r <= b) {
        return upper_bound(data[k].begin(), data[k].end(), x) - data[k].begin();
      } else {
        int lc = r_query(a, b, x, 2*k+1, l, (l+r)/2);
        int rc = r_query(a, b, x, 2*k+2, (l+r)/2, r);
        return lc + rc;
      }
    }
  public:
    kdTree(int n, int *d) {
      this->n = n;
      init(0, 0, n, d);
    }
    int query(int a, int b, int x) {
      return r_query(a, b, x, 0, 0, n);
    }
};