题目
题目链接：https://www.luogu.com.cn/problem/P4169
Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。
我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 \((x,y)\) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 \((x,y)\) ，那么她离近的天使玩偶可能埋下的地方有多远。
因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为 \(dist(A,B)=|A_x-B_x|+|A_y-B_y|\)。其中 \(A_x\) 表示点 \(A\) 的横坐标，其余类似。
思路
这个绝对值很烦，考虑分类讨论，分别求出娃娃位于 Ayu 左上、左下、右上、右下的最短距离。
以左上为例。当娃娃位于 Ayu 左上方时，设 Ayu 位于\((x,y)\)，娃娃位于\((p,q)\)，那么有\(|x-p|+|y-q|=x-y-(p-q)\)。我们要让这个玩意最小。
因为\(x-y\)是固定的，所以我们只要让\(p-q\)尽量大就行。
那么我们将询问和修改都看作一个四元组\((t,x,y,opt)\)，其中\(t\)是时间戳，\((x,y)\)是娃娃或 Ayu 的位置，\(opt\)表示这是询问还是修改。
那么我们对于每一个询问\((t_i,x_i,y_i,opt_i=2)\)，我们需要在满足\(_j<t_i,x_j\leq x_i,y_j\geq y_i,opt=1\)的所有的\(j\)中查找\(x_j+y_j\)最大的。这显然是一个三维偏序，只不过将个数改成了最大值。
那么就用与三维偏序基本相同的方法可以解决。
做完左上之后，仍然要做好左下、右上、右下。然后在其中求最小值。
我们发现，我们把整个坐标系顺时针旋转\(90\)°就可以将原来位于\((x,y)\)左上的点变到\((x,y)\)右上方。所以我么只要旋转3次，求4次答案即可。
这道题需要一些卡常。
加Ofast,inline。- 将每次合并时的分别将两个区间\(sort\)改为归并。
- 每次旋转之后需要将所有四元组重新按照时间戳排序，可以在最开始开一个数组，每次直接复制过去就可以了
- 如果不使用\((3)\)的方法，可以重载\(node\)的小于运算符，这样不用写\(cmp\)，会快一些的。
- 不要使用线段树来求区间最值，常数过大。可以使用树状数组来求。
代码
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline") //不会卡常啊，只能用物理性卡常了
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=300010,M=1000010,Inf=1e9;
int n,m,maxn;
inline int read()
{
int d=0,f=1; char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d*f;
}
struct node
{
int t,x,y,ans,opt;
}a[N*2],b[N*2];
inline bool operator < (const node &a,const node &b)
{
return a.t<b.t;
}
struct BIT
{
int c[M];
inline void update(int x,int val)
{
if (!x) return;
for (;x<=maxn;x+=x&-x)
c[x]=max(c[x],val);
}
inline int ask(int x)
{
int ans=0;
for (;x;x-=x&-x)
ans=max(ans,c[x]);
return ans;
}
inline void clear(int x)
{
for (;x<=maxn && c[x];x+=x&-x)
c[x]=0;
}
}bit;
inline void spin()
{
for (register int i=1;i<=n+m;i++)
{
swap(a[i].x,a[i].y);
a[i].y=M-9-a[i].y;
maxn=max(maxn,max(a[i].x,a[i].y));
}
}
inline void cdq(int l,int r) //上文是以左上为例，实际写的是左下，相对好些一些。
{
if (l==r) return;
int mid=(l+r)>>1,i=l,mn=Inf;
cdq(l,mid); cdq(mid+1,r);
for (register int j=mid+1;j<=r;j++)
{
if (a[j].opt==1) continue;
for (;a[i].x<=a[j].x && i<=mid;i++)
if (a[i].opt==1)
{
bit.update(a[i].y,a[i].x+a[i].y);
if (a[i].y<mn) mn=a[i].y;
}
if (mn<=a[j].y)
a[j].ans=min(a[j].ans,a[j].x+a[j].y-bit.ask(a[j].y));
}
for (register int j=l;j<i;j++)
if (a[j].opt==1) bit.clear(a[j].y);
int p=l,q=mid+1,tot=0;
for (;p<=mid && q<=r;)
if (a[p].x<a[q].x) b[++tot]=a[p],p++;
else b[++tot]=a[q],q++;
for (;p<=mid;p++) b[++tot]=a[p];
for (;q<=r;q++) b[++tot]=a[q];
for (int j=l;j<=r;j++)
a[j]=b[j-l+1];
}
int main()
{
n=read(); m=read();
for (register int i=1;i<=n;i++)
{
a[i].x=read(); a[i].y=read();
a[i].t=i; a[i].opt=1;
maxn=max(maxn,max(a[i].x,a[i].y));
}
for (register int i=n+1;i<=n+m;i++)
{
a[i].opt=read(); a[i].x=read(); a[i].y=read();
a[i].t=i; a[i].ans=Inf;
maxn=max(maxn,max(a[i].x,a[i].y));
}
sort(a+1,a+1+n+m); cdq(1,n+m); spin();
sort(a+1,a+1+n+m); cdq(1,n+m); spin();
sort(a+1,a+1+n+m); cdq(1,n+m); spin();
sort(a+1,a+1+n+m); cdq(1,n+m);
sort(a+1,a+1+n+m);
for (register int i=1;i<=n+m;i++)
if (a[i].opt==2) printf("%d\n",a[i].ans);
return 0;
}