[KD-tree]Rectangle

Rectangle

Time Limit: 50 Sec Memory Limit: 512 MB

Description

Input

Output

Sample Input

0
　　4
　　2 0
　　2 1
　　1 1
　　1 2
　　4
　　0 0 2 2
　　1 1 2 2
　　1 0 2 1
　　0 0 1 1

Sample Output

2 3
　　2 2
　　2 2
　　1 1

HINT

Solution

显然，如果我们求出了 last[i] 表示 在某个相同横/纵坐标下，前一个纵/横坐标的取值，那问题就转化为了三维偏序，且要求在线。

限制显然形如：L1 <= xi <= R1, L2 <= yi <= R2, last_i <= L3。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 500005;
const int Max = 500000;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}
int T, n;

struct node {int x, y;} fir[ONE];
bool cmp_x(const node &a, const node &b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
bool cmp_y(const node &a, const node &b) {return a.y < b.y || (a.y == b.y && a.x < b.x);}

struct power {int c[3];};
bool cmp_0(const power &a, const power &b) {return a.c[0] < b.c[0];}
bool cmp_1(const power &a, const power &b) {return a.c[1] < b.c[1];}
bool cmp_2(const power &a, const power &b) {return a.c[2] < b.c[2];}

int Ans;
struct ID
{
    struct point {int lc, rc, size, l[3], r[3];} p[ONE];
    power a[ONE];

    int kd_num;
    void Update(point &x)
    {
        if(x.lc) x.size += p[x.lc].size;
        if(x.rc) x.size += p[x.rc].size;
        point y;
        if(x.lc) y = p[x.lc],
        x.l[0] = min(x.l[0], y.l[0]), x.r[0] = max(x.r[0], y.r[0]),
        x.l[1] = min(x.l[1], y.l[1]), x.r[1] = max(x.r[1], y.r[1]),
        x.l[2] = min(x.l[2], y.l[2]), x.r[2] = max(x.r[2], y.r[2]);
        if(x.rc) y = p[x.rc],
        x.l[0] = min(x.l[0], y.l[0]), x.r[0] = max(x.r[0], y.r[0]),
        x.l[1] = min(x.l[1], y.l[1]), x.r[1] = max(x.r[1], y.r[1]),
        x.l[2] = min(x.l[2], y.l[2]), x.r[2] = max(x.r[2], y.r[2]);
    }

    s64 calc(int l, int r, int id)
    {
        s64 x = 0, xx = 0;
        for(int i = l; i <= r; i++)
            x += a[i].c[id], xx += (s64)a[i].c[id] * a[i].c[id];
        return (r - l + 1) * xx - x * x;
    }

    int root;
    int Build(int l, int r)
    {
        int mid = l + r >> 1;
        point &x = p[mid];

        s64 w0 = calc(l, r, 0), w1 = calc(l, r, 1), w2 = calc(l, r, 2);
        s64 w = max(w0, max(w1, w2));

        if(w == w0) nth_element(a + l, a + mid, a + r + 1, cmp_0);
        else
            if(w == w1) nth_element(a + l, a + mid, a + r + 1, cmp_1);
        else
            if(w == w2) nth_element(a + l, a + mid, a + r + 1, cmp_2);

        if(l < mid) x.lc = Build(l, mid - 1);
        if(mid < r) x.rc = Build(mid + 1, r);

        x.size = 1;
        x.l[0] = x.r[0] = a[mid].c[0];
        x.l[1] = x.r[1] = a[mid].c[1];
        x.l[2] = x.r[2] = a[mid].c[2];
        Update(x);
        return mid;
    }

    bool insect(const point &a, const point &b)
    {
        if(a.r[0] < b.l[0] || b.r[0] < a.l[0]) return 0;
        if(a.r[1] < b.l[1] || b.r[1] < a.l[1]) return 0;
        if(a.r[2] < b.l[2] || b.r[2] < a.l[2]) return 0;
        return 1;
    }

    bool contain(const point &a, const point &b)
    {
        if(!(a.l[0] <= b.l[0] && b.r[0] <= a.r[0])) return 0;
        if(!(a.l[1] <= b.l[1] && b.r[1] <= a.r[1])) return 0;
        if(!(a.l[2] <= b.l[2] && b.r[2] <= a.r[2])) return 0;
        return 1;
    }

    bool contain(const point &a, const power &b)
    {
        if(!(a.l[0] <= b.c[0] && b.c[0] <= a.r[0])) return 0;
        if(!(a.l[1] <= b.c[1] && b.c[1] <= a.r[1])) return 0;
        if(!(a.l[2] <= b.c[2] && b.c[2] <= a.r[2])) return 0;
        return 1;
    }

    void Query(int i, const point &x)
    {
        point now = p[i];
        if(!insect(x, now)) return;
        if(contain(x, now)) {Ans += now.size; return;}
        if(contain(x, a[i])) Ans++;
        if(now.lc) Query(now.lc, x);
        if(now.rc) Query(now.rc, x);
    }
};
ID A, B;


void Make_1()//|
{
    sort(fir + 1, fir + n + 1, cmp_y);
    static int last[ONE];
    for(int i = 0; i <= Max; i++) last[i] = -1;
    for(int i = 1; i <= n; i++)
    {
        A.a[i].c[0] = fir[i].x;
        A.a[i].c[1] = fir[i].y;
        A.a[i].c[2] = last[fir[i].x];
        last[fir[i].x] = fir[i].y;
    }
    A.root = A.Build(1, n);
}

void Make_2()
{
    sort(fir + 1, fir + n + 1, cmp_x);
    static int last[ONE];
    for(int i = 0; i <= Max; i++) last[i] = -1;
    for(int i = 1; i <= n; i++)
    {
        B.a[i].c[0] = fir[i].x;
        B.a[i].c[1] = fir[i].y;
        B.a[i].c[2] = last[fir[i].y];
        last[fir[i].y] = fir[i].x;
    }
    B.root = B.Build(1, n);
}

int main()
{
    T = get(), n = get();
    for(int i = 1; i <= n; i++)
        fir[i].x = get(), fir[i].y = get();
    Make_1(), Make_2();
    int Q = get(), lax = 0, lay = 0;
    while(Q--)
    {
        int x_1 = get(), y_1 = get(), x_2 = get(), y_2 = get();
        x_1 = x_1 + (lax + lay) * T, y_1 = y_1 + (lax + lay) * T;
        x_2 = x_2 + (lax + lay) * T, y_2 = y_2 + (lax + lay) * T;
        ID::point x;

        Ans = x.size = x.lc = x.rc = 0;
        x.l[0] = x_1, x.r[0] = x_2, x.l[1] = y_1, x.r[1] = y_2;
        x.l[2] = -1, x.r[2] = y_1 - 1;
        A.Query(A.root, x), lax = Ans;

        Ans = x.size = x.lc = x.rc = 0;
        x.l[0] = x_1, x.r[0] = x_2, x.l[1] = y_1, x.r[1] = y_2;
        x.l[2] = -1, x.r[2] = x_1 - 1;
        B.Query(B.root, x), lay = Ans;

        printf("%d %d\n", lax, lay);
    }
}