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;
}