P6224 [BJWC2014]数据 题解
JiaY19
·
·
题解
\text{可能更好的阅读体验}
明明是一道 \text{k-d tree} 模板题，为什么写的人这么少呢。
思路
看到平面上的操作，就必不可免的想到 \text{k-d tree}。
**1.最远**
我们可以发现，一个点到一个矩阵的最远距离一定是到其四个角的最大距离，$\text{k-d tree}$ 维护的矩阵虽然不是一个实际的矩阵，但算出这个答案与原来的答案进行比较，也能剪枝掉不少情况。
**2.最近**
一个点到一个矩阵的最近距离我们发现，如果点在矩阵内，那么就是零，不然就是直接到边或者到四个角。
为了简便，我们可以这么写：
```cpp
inline int ask(int x , int y , int id)
{
int res = 0;
res += max(0ll , y - t[id].u) + max(0ll , x - t[id].r);
res += max(0ll , t[id].d - y) + max(0ll , t[id].l - x);
return res;
}
```
本题实测是不需要方差建树和重构树的，直接交替建树就可以了。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200020;
const int inf = 1e10;
int n , m , rt , cnt , top , ans , stk[N];
struct Node
{
int l , r , u , d , siz , a[2] , son[2];
}t[N];
inline int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
inline void push_up(int p)
{
t[p].l = t[p].r = t[p].a[0] , t[p].u = t[p].d = t[p].a[1] , t[p].siz = 1;
for(int i = 0;i <= 1;i++) if(t[p].son[i])
t[p].siz += t[t[p].son[i]].siz,
t[p].l = min(t[p].l , t[t[p].son[i]].l) , t[p].r = max(t[p].r , t[t[p].son[i]].r),
t[p].d = min(t[p].d , t[t[p].son[i]].d) , t[p].u = max(t[p].u , t[t[p].son[i]].u);
}
inline void insert(int &p , int id , int opt)
{
if(!p) { p = id , push_up(p); return; }
if(t[id].a[opt] < t[p].a[opt]) insert(t[p].son[0] , id , opt ^ 1);
else insert(t[p].son[1] , id , opt ^ 1); push_up(p);
}
inline void ask1(int p , int x , int y)
{
ans = max(ans , abs(x - t[p].a[0]) + abs(y - t[p].a[1]));
for(int i = 0;i <= 1;i++)
if(t[p].son[i])
{
int l = t[p].l , r = t[p].r , u = t[p].u , d = t[p].d;
int res = max({abs(l - x) + abs(u - y) , abs(r - x) + abs(u - y) , abs(r - x) + abs(d - y) , abs(l - x) + abs(d - y)});
if(res > ans) ask1(t[p].son[i] , x , y);
}
}
inline int ask(int x , int y , int id)
{
int res = 0;
res += max(0ll , y - t[id].u) + max(0ll , x - t[id].r);
res += max(0ll , t[id].d - y) + max(0ll , t[id].l - x);
return res;
}
inline void ask2(int p , int x , int y)
{
ans = min(ans , abs(x - t[p].a[0]) + abs(y - t[p].a[1]));
for(int i = 0;i <= 1;i++)
if(t[p].son[i])
{
int res = ask(x , y , t[p].son[i]);
if(res < ans) ask2(t[p].son[i] , x , y);
}
}
signed main()
{
n = read();
for(int i = 1;i <= n;i++)
{
int x = read() , y = read(); ++cnt;
t[cnt].a[0] = x , t[cnt].a[1] = y;
insert(rt , cnt , 1);
}
m = read();
for(int i = 1;i <= m;i++)
{
int opt = read() , x = read() , y = read();
if(opt == 0)
{
t[++cnt].a[0] = x , t[cnt].a[1] = y;
insert(rt , cnt , 1);
}
if(opt == 1) ans = inf , ask2(rt , x , y) , printf("%lld\n" , ans);
if(opt == 2) ans = -inf , ask1(rt , x , y) , printf("%lld\n" , ans);
}
return 0;
}
```