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

CDQ分治的题目.

我们发现题目要我们求的\(|A_x-B_x|+|A_y-B_y|\)的绝对值号比较恶心.

试想一下怎么去掉

如果所有的点都在我们当前求的点的左下方(就是只考虑在他坐下方的点对他的贡献). 我们怎么求?

那么就要我们求\(min{A_x-B_x+A_y-B_y}\)(假设\(A\)为询问的点)

那么其实就是让我们求\(A_x+A_y-max(B_x+B_y)\)

也因为要满足左下角的限制

其实就是满足

\(B_x<=A_x\)同时满足\(B_y<=A_y\)中最大的\(B_x+B_y\)

这个是可以直接CDQ的

但是我们只考虑了左下方的点对他的贡献,很明显,这是不够的

那么我们就想办法依次将左上,右上,右下全部转化为左下

就是通过同最大值域的加减来改变他们的左边但不改变相对关系

注意常数就好了

另外,这种情况下归并排序的时间复杂度比快排优秀太多了

#include<bits/stdc++.h>

using namespace std;

const int N = 6e5 + 3;

const int M = 1e6 + 3;

const int INF = 2e9;

int n,m;

int max_x,max_y;

int ans[N];

struct Q{

    int type;

    int id;

    int xi;

    int yi;

    int ans;

}q[N],p[N],h[N];

Q g[N];

struct BIT{

    int c[M];

    inline void ins(int x,int v){

        for(;x <= max_y;x += x & -x) c[x] = max(c[x],v);

    }

    inline int query(int x){

        int res = 0;

        for(;x;x -= x & -x) res = max(res,c[x]);

        return res;

    }

    inline void clear(int x){

        for(;x <= max_y;x += x & -x) c[x] = 0;

    }

}T;

int xx[N],yy[N];

inline bool cmp1(Q x,Q y){

    return x.id < y.id;

}

inline bool cmp2(Q x,Q y){

    if(x.xi != y.xi)

    return x.xi < y.xi;

    return x.yi < y.yi;

}

inline int read(){

    int x = 0;int flag = 0;

    char ch = getchar();

    while(!isdigit(ch)){

        if(ch == '-') flag = 1;

        ch = getchar();

    }

    while(isdigit(ch)){

        x = (x<<1) + (x<<3) + (ch^'0');

        ch = getchar();

    }

    if(flag) x = -x;

    return x;

}

inline void solve(int l,int r){

    if(l == r) return;

    int mid = (l + r) >> 1;

    solve(l,mid);solve(mid + 1,r);

    //sort(p + l,p + mid + 1,cmp2);

    //sort(p + mid + 1,p + r + 1,cmp2);

	// nj  printf("%d %d\n",l,r);

    int now = l;

    int ll = l,rr = mid + 1,nn = l - 1;

   // cout << 1 << endl;

    for(int i = mid + 1;i <= r;++i){

        while(i <= r && p[i].type != 2) ++i;

        if(i > r) break;

        for(;now <= mid && p[now].xi <= p[i].xi;++now) if(p[now].type == 1) T.ins(p[now].yi,p[now].xi + p[now].yi);

        int t = T.query(p[i].yi);

        if(t) ans[p[i].id] = min(ans[p[i].id],p[i].xi + p[i].yi - t);

    }

    for(int i = l;i < now;++i) if(p[i].type == 1) T.clear(p[i].yi);

     while(ll <= mid && rr <= r){

    	if(p[ll].xi <= p[rr].xi) h[++nn] = p[ll++];

		else h[++nn] = p[rr++];

    }

	while(ll <= mid) h[++nn] = p[ll++];

    while(rr <= r) h[++nn] = p[rr++];

    for(int i = l;i <= r;++i) p[i] = h[i];

}

inline void del(){

    int rx = 0,ry = 0;m = 0;

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

        if(p[i].type == 1) rx = max(p[i].xi,rx),ry = max(p[i].yi,ry);

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

        if((p[i].xi <= rx && p[i].yi <= ry) || p[i].type == 2) g[++m] = p[i];

    }

    for(int i = 1;i <= m;++i) p[i] = g[i];

}

int main(){

    n = read(),m = read();

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

        q[i].xi = read() + 1,q[i].yi = read() + 1;

        max_x = max(max_x,q[i].xi),max_y = max(max_y,q[i].yi);

        q[i].id = i;

        q[i].type = 1;

    }

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

        q[n + i].type = read();q[n + i].xi = read() + 1;q[n + i].yi = read() + 1;

        q[n + i].id = i + n;

        max_x = max(max_x,q[n + i].xi),max_y = max(max_y,q[n + i].yi);

    }

    n += m;

    for(int i = 1;i <= n;++i) p[i] = q[i];

    for(int i = 1;i <= n;++i) ans[i] = INF;

    max_y = max(max_x,max_y) + 1;

    solve(1,n);

    for(int i = 1;i <= n;++i) p[i] = q[i],p[i].xi = max_y - p[i].xi;

    solve(1,n);

    for(int i = 1;i <= n;++i) p[i] = q[i],p[i].yi = max_y - p[i].yi;

    solve(1,n);

    for(int i = 1;i <= n;++i) p[i] = q[i],p[i].xi = max_y - p[i].xi,p[i].yi = max_y - p[i].yi;

    solve(1,n);

    for(int i = 1;i <= n;++i) if(ans[i] != INF) printf("%d\n",ans[i]);

    return 0;

}

巴特西

天使玩偶/SJY摆棋子

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

最新文章

热门文章