[Violet]天使玩偶/SJY摆棋子

题目传送门

解题思路

用CDQ分治开了氧气跑过。

将输入给的顺序作为第一维的时间，x为第二维，y为第三维。对于距离一个询问(ax,ay)，将询问分为四块，左上，右上，左下，右下，对于坐下，左下的dist即为ax+ay-max(bx+by)。所以只要查询时间小于自己的点里x+y最大的即可。对于其他四块，都可以转为左下，各自跑一遍CDQ。

代码如下

#include <bits/stdc++.h>

using namespace std;

int n, m;

const int N = 1e6+5;

struct T{

    int t, x, y;

    bool f;

    T(){}

    T(int t, int x, int y, bool f): t(t), x(x), y(y), f(f){}

}v[N], t[N], a[N];

int c[N];

int lowbit(int x)

{

    return x & (-x);

}

void update(int x, int v)

{

    for(int i = x; i < N; i += lowbit(i))

        c[i] = max(c[i], v);

}

int query(int x)

{

    int ans = -1;

    for(int i = x; i > 0; i -= lowbit(i)){

        ans = max(c[i], ans);

    }

    return ans;

}

void clear(int x)

{

    for(int i = x; i < N; i += lowbit(i))

        c[i] = 0;

}

int ans[N];

void CDQ(int l, int r)

{

    if(l == r)

        return;

    int mid = (l + r) / 2;

    CDQ(l, mid);

    CDQ(mid + 1, r);

    for(int i = l; i <= r; i ++)

        t[i] = v[i];

    int x = l, y = mid + 1;

    int cnt = l - 1;

    while(x <= mid || y <= r){

        if(x <= mid && y <= r){

            if(t[x].x <= t[y].x){

                if(!t[x].f)update(t[x].y, t[x].x + t[x].y);

                v[++cnt] = t[x];

                ++x;

            }

            else {

                int r = query(t[y].y);

                if(t[y].f && r) ans[t[y].t] = min(ans[t[y].t], t[y].x + t[y].y - r);

                v[++cnt] = t[y];

                ++y;

            }

        }

        else if(x <= mid){

            if(!t[x].f)update(t[x].y, t[x].x + t[x].y);

            v[++cnt] = t[x];

            ++x;

        }

        else {

            int r = query(t[y].y);

            if(t[y].f && r) ans[t[y].t] = min(ans[t[y].t], t[y].x + t[y].y - r);

            v[++cnt] = t[y];

            ++y;

        }

    }

    for(int i = l; i <= mid; i ++)

        if(!t[i].f)clear(t[i].y);

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++){

        int x, y;

        scanf("%d%d", &x, &y);

        v[i] = T(0, x + 1, y + 1, 0);

    }

    for(int i = 1; i <= m; i ++){

        int t, x, y;

        scanf("%d%d%d", &t, &x, &y);

        v[n+i] = T(i, x + 1, y + 1, t - 1);

    }

    int lx, ly;

    lx = ly = 0;

    for(int i = 1; i <= n + m; i ++){

        a[i] = v[i];

        lx = max(lx, v[i].x + 1);

        ly = max(ly, v[i].y + 1);

    }

    memset(ans, 0x3f, sizeof(ans));

    CDQ(1, n + m);

    for(int i = 1; i <= n + m; i ++){

        v[i] = a[i];

        v[i].x = lx - v[i].x;

    }

    CDQ(1, n + m);

    for(int i = 1; i <= n + m; i ++){

        v[i] = a[i];

        v[i].y = ly - v[i].y;

    }

    CDQ(1, n + m);

    for(int i = 1; i <= n + m; i ++){

        v[i] = a[i];

        v[i].x = lx - v[i].x;

        v[i].y = ly - v[i].y;

    }

    CDQ(1, n + m);

    for(int i = 1; i <= m; i ++){

        if(a[i + n].f)

            printf("%d\n", ans[i]);

    }

    return 0;

}