AOJ DSL_2_C kD tree

Prob.

给二维平面的一些点，求某个矩形内所有点的下标。

Sol.

k-d 裸题。
有空再写教程吧……这次就算了。

Code(160ms 22284kB)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 5e5 + 100;
int D; int n, root; 
struct Point
{
    int d[2], l, r, num;
    Point(){l = 0, r = 0;}
    int& operator[](int i){return d[i];}
    bool operator<(const Point& p)const{return d[D] < p.d[D];}
} P[maxn], t[maxn];
int tc = 1;
int build(int L = 0, int R = n - 1, int d = 0)
{
    int M = (L + R) >> 1;
    D = d;
    nth_element(P + L, P + M, P + R + 1);
    int o = tc++;
    t[o] = P[M];
    if(L < M) t[o].l = build(L, M - 1, d ^ 1);
    if(M < R) t[o].r = build(M + 1, R, d ^ 1);
    return o;
}
int sx, tx, sy, ty; vector<int> ans;
void find(int o = root, int d = 0)
{
    if(sx <= t[o].d[0] && t[o].d[0] <= tx && sy <= t[o].d[1] && t[o].d[1] <= ty)
        ans.push_back(t[o].num);
    if(d == 0)
    {
        if(t[o].l && sx <= t[o][0]) find(t[o].l, d ^ 1);
        if(t[o].r && t[o][0] <= tx) find(t[o].r, d ^ 1);
    }
    else
    {
        if(t[o].l && sy <= t[o][1]) find(t[o].l, d ^ 1);
        if(t[o].r && t[o][1] <= ty) find(t[o].r, d ^ 1);
    }
}
int main()
{
    read(n);
    for(int i = 0; i < n; ++i) read(P[i][0], P[i][1]), P[i].num = i;
    root = build();
    int q; read(q);
    while(q--)
    {
        ans.clear();
        read(sx, tx), read(sy, ty);
        find();
        sort(ans.begin(), ans.end());
        for(int i = 0; i < ans.size(); ++i) printf("%d\n", ans[i]);
        puts("");
    }
    return 0;
}