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

传送门

二维平面修改+查询，cdq分治可以解决。

求关于某个点曼哈顿距离（x,y坐标）最近的点——dis(A,B) = |Ax-Bx|+|Ay-By|

但是如何去掉绝对值呢？

查看题解发现假设所有的点都在查询点的左下方，dis(A,B) = (Ax-Bx)+(Ay-By) = (Ax+Ay)-(Bx+By)

只要求满足Bx<Ax,By<Ay且Bx,By之和最大的点就好了。

那么如何把所有的点转化到该查询的左下呢？

对于每个查询，可以把一、二、四象限的点都通过对称转移到第三象限。但查询很多，不可能一个个翻转。

换个思路，如果把整个平面翻转三次，进行四次cdq分治，每次都只考虑左下的点，所有的点就都遍历到了！

记录最大的x或y值为边界len，每次沿len翻转。例如沿y轴翻转时，x = len-x

那么每个操作有三维——时间、x坐标、y坐标

时间在输入时已经排好了；x归并排序；y仿照陌上花开，用树状数组记录。

优化 & 注意

这道题坑点超级多...而且四次cdq分治会得到一个感人的复杂度，所以必须考虑优化，卡一卡常数（我选择吸氧）

cdq内的归并排序代替每次sort。
因为每次cdq完顺序会被打乱，如果重新按时间O(nlogn)排序，不如每次存入一个临时数组，然后O(n)直接复制过去。

　　但是ans需要存入初始的数组中，所以结构体需要一个.id来记录打乱前的时间，也就是原数组下标。赋值应该写a[b[t2].id].ans，而不是a[t2].ans。

　　并且，由于每次查询点的x,y也会更改，所以ans里不能直接存max(Bx+By)，而应该为min((Ax+Ay)-(Bx+By))。

如果某个点在坐标轴上，那么它的x或y为0。存入树状数组时，会因为lowbit()==0而陷入死循环。所以存入时，将x,y分别+1。

　　同样的，如果某个点在翻转边界len上，翻转时也会变为0。所以len也要++。

考虑这样一种情况：某一点非常靠近边界，导致某次翻转时，没有点在它的左下。这样查询时默认返回了0。

　　当前的“原点”比实际上的点离该查询点更近，这样最终的距离就成了这个点到原点的距离，但原点是不存在的（经过刚刚的更改，已经没有x或y坐标为0的点）

　　为避免这种情况，当查询时需要特判，若为0则返回-INF。

由于初始值——前n个点一定是修改操作，可以把它们直接排好序，不用递归检验是否有查询。（不过我觉得有点麻烦就没写）

这道题的代码不难，但是细节特别多，很难debug...写的时候思路一定要清晰了！

代码如下

// luogu-judger-enable-o2

#include<cstdio>

#include<iostream>

#define MogeKo qwq

using namespace std;

const int maxn = 1e7+;

const int INF = 2e7+;

int n,q,opt,x,y,len;

struct node {

    int x,y,type,id,ans;

} a[maxn],b[maxn],tem[maxn];

struct BIT {

    int m[maxn];

    int lowbit(int x) {

        return x & -x;

    }

    void update(int x,int v) {

        for(; x <= len; x+= lowbit(x))

            m[x] = max(m[x],v);

    }

    int query(int x) {

        int ans = ;

        for(; x; x-=lowbit(x))

            ans = max(ans,m[x]);

        return ans?ans:-INF;

    }

    void clear(int x) {

        for(; m[x]; x+= lowbit(x))

            m[x] = ;

    }

} tree;

void cdq(int L,int R) {

    if(L == R) return;

    int mid = L+R >> ;

    cdq(L,mid),cdq(mid+,R);

    int t1 = L,t2 = mid+;

    int k = L;

    while(t2 <= R) {

        while(t1 <= mid && b[t1].x <= b[t2].x) {

            if(b[t1].type == )

                tree.update(b[t1].y, b[t1].x+b[t1].y);

            tem[k++] = b[t1++];

        }

        if(b[t2].type == )

            a[b[t2].id].ans = min(a[b[t2].id].ans,b[t2].x+b[t2].y-tree.query(b[t2].y));

        tem[k++] = b[t2++];

    }

    for(int i = L; i <= t1-; i++)

        if(b[i].type == ) tree.clear(b[i].y);

    while(t1 <= mid) tem[k++] = b[t1++];

    for(int i = L;i <= R;i++) b[i] = tem[i];

}

void solve(int rx,int ry) {

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

        b[i] = a[i];

        if(rx) b[i].x = len - b[i].x;

        if(ry) b[i].y = len - b[i].y;

    }

    cdq(,n+q);

}

int main() {

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

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

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

        a[i].type = ;

        a[i].id = i;

        a[i].x = ++x;

        a[i].y = ++y;

        len = max(len,max(x,y));

    }

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

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

        a[i].type = opt;

        a[i].id = i;

        a[i].x = ++x;

        a[i].y = ++y;

        a[i].ans = INF;

        len = max(len,max(x,y));

    }

    len++;

    solve(,),solve(,),solve(,),solve(,);

    for(int i = n+; i <= n+q; i++)

        if(a[i].type == ) printf("%d\n",a[i].ans);

    return ;

}

巴特西

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

最新文章

热门文章