BZOJ2716 [Violet 3]天使玩偶 【CDQ分治】

题目

输入格式

输出格式

输入样例

//样例太长就不贴了。。。。

输出样例

//见原题

提示

题解

我们将曼哈顿距离式子中的绝对值去掉，每次只考虑x,y比当前点小的更新答案。

为了使所有点都对答案进行更新，将坐标轴旋转三次再算三次

每一次对于点(x,y)，找到(x’,y’)【x’<=x，y’<= y且 时间t’ < t】使得x+y−(x′+y′)最小

类似三维偏序的东西，可以用CDQ分治

树状数组维护最大值

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define lbt(x) (x & -x)

using namespace std;

const int maxn = 1000005,maxm = 2010005,INF = 0x7fffffff;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int ans[maxn],n,m,N = 0,ansi = 0,Qi = 0,S[maxm];

struct Que{int x,y,t,id;}Q[maxn],T[maxn];

inline bool operator <(const Que& a,const Que& b){

    if (a.x == b.x && a.y == b.y) return a.t < b.t;

    if (a.x == b.x) return a.y < b.y;

    return a.x < b.x;

}

void add(int u,int v){while (u <= N) S[u] = max(S[u],v),u += lbt(u);}

int query(int u){int an = 0; while (u) an = max(an,S[u]),u -= lbt(u); return an;}

void cls(int u){while (u <= N) S[u] = 0,u += lbt(u);}

void CDQ(int l,int r){

    if (l == r) return;

    int mid = l + r >> 1,l1 = l,l2 = mid + 1,temp;

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

        if (Q[i].t <= mid && !Q[i].id)

            add(Q[i].y,Q[i].x + Q[i].y);

        else if (Q[i].t > mid && Q[i].id){

            temp = query(Q[i].y);

            if (temp) ans[Q[i].id] = min(ans[Q[i].id],Q[i].x + Q[i].y - temp);

        }

    }

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

        if (Q[i].t <= mid){

            T[l1++] = Q[i];

            if (!Q[i].id) cls(Q[i].y);

        }else T[l2++] = Q[i];

    }

    for (int i = l; i <= r; i++) Q[i] = T[i];

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

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out1.txt","w",stdout);

    n = RD();m = RD(); Qi = n + m; int opt;

    REP(i,n){

        Q[i].x = RD() + 1,Q[i].y = RD() + 1,Q[i].t = i,Q[i].id = 0;

        N = max(N,Q[i].x); N = max(N,Q[i].y);

    }

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

        opt = RD(); Q[i].x = RD() + 1; Q[i].y = RD() + 1,Q[i].t = i;

        N = max(N,Q[i].x); N = max(N,Q[i].y);

        if (opt & 1) Q[i].id = 0;

        else Q[i].id = ++ansi;

    }N++;

    fill(ans,ans + maxn,INF);

    sort(Q + 1,Q + 1 + Qi); CDQ(1,Qi);

    REP(i,Qi) Q[i].x = N - Q[i].x;

    sort(Q + 1,Q + 1 + Qi); CDQ(1,Qi);

    REP(i,Qi) Q[i].y = N - Q[i].y;

    sort(Q + 1,Q + 1 + Qi); CDQ(1,Qi);

    REP(i,Qi) Q[i].x = N - Q[i].x;

    sort(Q + 1,Q + 1 + Qi); CDQ(1,Qi);

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

    return 0;

}