Problem
Solution
考虑静态
对于每一组询问((x,y))和现在已经确定的点(P = {(x_i,y_i)})，答案即为：
(min_{1 le i le |P|}{|x - x_i| + |y - y_i|})
发现有绝对值不太好整，考虑拆开，分成四种情况：
(min_{1 le i le |P|,x_i le x,y_i le y} {x + y - (x_i + y_i)})
(min_{1 le i le |P|,x_i ge x,y_i le y} {y - x - (y_i - x_i)})
(min_{1 le i le |P|,x_i le x,y_i ge y} {x - y - (x_i - y_i)})
(min_{1 le i le |P|,x_i ge x,y_i ge y} {-x - y - (-x_i - y_i)})
然后取最小值。
对于每个情况，变成了一个二位偏序，直接排序+BIT即可，BIT里面维护的是(dx cdot x + dy cdot y)的最大值，下标为(y)，(dx,dy)按情况决定，例如第一个情况就是(dx = 1,dy = 1).
如果有多组询问，那么就将询问和修改放在一起，然后按照(x)排序即可。
化动为静
使用cdq分治，对于cdq(l,r)，先解决cdq(l,mid)和cdq(mid + 1,r)，然后考虑左边的修改对右边询问的影响。
这时候就可以转化问题：上面提到的(P)集合就是([l,mid])中的修改，询问就是([mid + 1,r])中的询问，进行四个情况分别处理即可。
Code
# include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 5,MAXY = 1e6 + 5;
const int inf = 0x3f3f3f3f;
int n,m;
int Maxy = 0;
struct Point
{
int x,y;
Point() {}
Point(int _x,int _y) : x(_x),y(_y) {}
};
struct query
{
int t,x,y;
}Q[N],b[N];
int ans[N];
template <typename T> void read(T &x)
{
int w = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') w = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
x *= w;
return;
}
void write(int x)
{
if(x < 0) putchar('-'),x = -x;
if(x >= 10) write(x / 10);
char ch = (x % 10) + 48;
putchar(ch);
return;
}
struct BIT
{
int A[MAXY];
int lowbit(int x) {return x & (-x);}
void add(int x,int d)
{
while(x <= Maxy)
{
A[x] = max(A[x],d);
x += lowbit(x);
}
return;
}
int query(int x)
{
int ans = -inf;
while(x)
{
ans = max(ans,A[x]);
x -= lowbit(x);
}
return ans;
}
void clear(int x,int d)
{
while(x <= Maxy)
{
A[x] = d;
x += lowbit(x);
}
return;
}
}T;
bool compare(const struct query &x,const struct query &y)
{
if(x.x == y.x) return x.y < y.y;
return x.x < y.x;
}
void solve(int l,int r,int opt) /*opt = 0 左下 opt = 1 左上 opt = 2 右下 opt = 3 右上*/
{
if(opt == 0)
{
for(int i = l; i <= r; i++)
{
int sum = b[i].x + b[i].y;
if(Q[b[i].t].t == 1)
{
T.add(b[i].y,sum);
}
else ans[b[i].t] = min(ans[b[i].t],abs(sum - T.query(b[i].y)));
}
for(int i = l; i <= r; i++) if(Q[b[i].t].t == 1) T.clear(b[i].y,-inf);
}
else if(opt == 1)
{
for(int i = l; i <= r; i++)
{
int sum = b[i].x - b[i].y;
if(Q[b[i].t].t == 1)
{
T.add(Maxy - b[i].y,sum);
}
else ans[b[i].t] = min(ans[b[i].t],abs(sum - T.query(Maxy - b[i].y)));
}
for(int i = l; i <= r; i++)
{
if(Q[b[i].t].t == 1) T.clear(Maxy - b[i].y,-inf);
}
}
else if(opt == 2)
{
for(int i = r; i >= l; i--)
{
int sum = b[i].y - b[i].x;
if(Q[b[i].t].t == 1)
{
T.add(b[i].y,sum);
}
else ans[b[i].t] = min(ans[b[i].t],abs(sum - T.query(b[i].y)));
}
for(int i = r; i >= l; i--)
{
if(Q[b[i].t].t == 1) T.clear(b[i].y,-inf);
}
}
else
{
for(int i = r; i >= l;i--)
{
int sum = -b[i].x - b[i].y;
if(Q[b[i].t].t == 1)
{
T.add(Maxy - b[i].y,sum);
}
else ans[b[i].t] = min(ans[b[i].t],abs(sum - T.query(Maxy - b[i].y)));
}
for(int i = r; i >= l; i--)
{
if(Q[b[i].t].t == 1) T.clear(Maxy - b[i].y,-inf);
}
}
return;
}
void CDQ(int l,int r)
{
if(l >= r) return;
int mid = (l + r) >> 1;
CDQ(l,mid),CDQ(mid + 1,r);
int tot = 0;
for(int i = l; i <= mid; i++)
{
if(Q[i].t == 1) b[++tot] = Q[i],b[tot].t = i;
}
for(int i = mid + 1; i <= r; i++)
{
if(Q[i].t == 2)
{
b[++tot] = Q[i];b[tot].t = i;
}
}
//将[l,mid]的修改和[mid + 1,r]的查询加入
sort(b + 1, b + tot + 1, compare);
for(int i = 0; i <= 3; i++) solve(1,tot,i);
return;
}
int main(void)
{
read(n),read(m);
for(int i = 1; i <= n; i++)
{
read(Q[i].x),read(Q[i].y);
++Q[i].x,++Q[i].y;
Q[i].t = 1;
Maxy = max(Maxy,Q[i].y);
}
for(int i = n + 1; i <= n + m; i++)
{
read(Q[i].t),read(Q[i].x),read(Q[i].y);
++Q[i].x,++Q[i].y;
Maxy = max(Maxy,Q[i].y);
}
++Maxy;
for(int i = 1; i <= n + m; i++) ans[i] = inf;
for(int i = 0; i <= Maxy; i++) T.A[i] = -inf;
CDQ(1,n + m);
for(int i = n + 1; i <= n + m; i++) if(Q[i].t == 2) {write(ans[i]);putchar('
');}
return 0;
}
Tricks
有一部分是要处理>部分的，因为这里的BIT维护的是最大值，所以不能用减的方法。考虑将整个树状数组倒序，第(i)个就变成了第(n - i)个，>也变成<，再进行处理即可。