天使玩偶
本题有若干个操作,会加入新的回忆点,或查询当前离他最近的一个回忆点的距离。
如果先忽略加入操作,那么每次查询与 $(x, y)$ 最近的点有多远,答案就是:$min \lbrace \vert x-x_i \vert + \vert y - y_i \vert \rbrace$
我们可以将绝对值去掉,将每个询问分成4个询问,分别询问 $(x, y)$ 的左下、左上、右下、右上方向上距离最近的点的距离,四个结果取一个最小值就是答案。
以左下为例,答案就是:$min \lbrace (x-x_i) + (y-y_i) \rbrace$
进一步化简,答案变成:$(x + y) - max \lbrace x_i + y_i \rbrace$
我们可以把 $n$ 个点的坐标和 $m$ 个询问的坐标一起按照横坐标从小到大排序。然后依次扫描。
对于左下方向来说:
1. 若扫描到一个点 $(x_i, y_i)$,则在树状数组(或线段树)中把第 $y_i$ 个位置上的值与 $x_i+y_i$ 取 $max$,同时维护前缀(或区间)最大值
2. 若扫描到一个查询 $(x, y)$,则在树状数组(或线段树)中查询 $[0,y]$ 上的最大值 $val$,该询问的答案就是$x + y - val$。
在上面做法中,排序满足了 $x_i \leq x$ 的条件,树状数组控制了 $y_i \leq y$ 的条件并维护了 $x_i + y_i$ 的最大值。
对于左上、右上和左下三个方向都和以上做法类似。例如左上方向,还是按照横坐标排序,这时应该是 $x_i \leq x, 10^6 - y_i \leq 10^6 - y$ -> $x_i \leq x, -y_i \leq y$,因此树状数组改成维护 $x_i-y_i$ 的最大值,修改时的位置变为 $10^6-y_i$,查询时的前缀变为 $[0, 10^6-y]$,剩下两个方向可自行推导。
到这里我们再加上加入操作,除了查询还可能在平面中添加点。有查询和插入操作的动态问题,这就可以用CDQ分治分成若干个静态小问题来解决。
那么我们每次递归完左、右区间之后还需要处理左区间修改对右区间查询的影响。可以把第 $l \sim mid$ 项操作中增加的点依次加入一个初始为空的平面,再考虑第 $mid + 1 \sim r$项操作中的查询,找到平面上距离最近的点来更新答案,可以用和上面一样的做法。
注意!为了保证每次的时间复杂度之和当前递归的区间内部相关,因此每次不能建立一个新的树状数组,必须在处理完每个区间后再将对树状数组的修改依次还原,保证每次进入和离开时,树状数组都是空的,可以复用。这样整个算法的时间复杂度为 $O((n + m) \log_2^2(n + m))$
注意! 本题会卡常,需要在CDQ分治时进行一些优化,如果区间中只存在添加操作,不存在查询操作,那么不需要处理左区间的修改操作对右区间的查询操作的影响。这是一步效果非常明显的优化(不加这步就只能吸氧了)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1000010, INF = 0x3f3f3f3f;
int n, m;
int tr[N], maxy; //树状数组(维护纵坐标的前缀最大值)、纵坐标的最大范围
int res[N]; //结果数组
struct Operator
{
int x, y, z;
bool operator< (const Operator &t) const //按横坐标从小到大排序
{
return x < t.x;
}
};
Operator a[N]; //原操作序列,(x, y, z) 表示坐标和类型
Operator b[N]; //静态问题的序列(按横坐标排序),(x, y, z) 表示坐标和在a[]序列中的下标
int lowbit(int x)
{
return x & -x;
}
void insert(int x, int c) //将 c 和第 x 个位置上的值取 max
{
for(int i = x; i <= maxy; i += lowbit(i)) tr[i] = max(tr[i], c);
}
int query(int x) //查询 [1 ~ x] 中的最大值
{
int res = -INF; //负无穷
for(int i = x; i; i -= lowbit(i)) res = max(res, tr[i]);
return res;
}
//从各个方向更新最近的距离,需要考虑b[st ~ ed - t]的坐标
//t 表示横坐标的偏移量,树状数组维护的信息用系数dx, dy(±1)指定
void work(int st, int ed, int t, int dx, int dy)
{
for(int i = st; i != ed; i += t)
{
int y;
if(dy == 1) y = b[i].y; //统计的是a[i]下方的点(再根据dx确定是左上还是右上)
else y = maxy - b[i].y + 1; //统计的是a[i]上方的点(再根据dx确定是左下还是右下)
int dist = dx * b[i].x + dy * b[i].y; //计算查询节点的曼哈顿距离
if(a[b[i].z].z == 1) insert(y, dist); //添加操作
else res[b[i].z] = min(res[b[i].z], abs(dist - query(y))); //查询操作(取当前节点和查询节点距离的最小值)
}
for(int i = st; i != ed; i += t)
{
int y;
if(dy == 1) y = b[i].y; //统计的是a[i]上方的点
else y = maxy - b[i].y + 1; //统计的是a[i]下方的点
if(a[b[i].z].z == 1) //添加操作需要还原
for(int j = y; j <= maxy; j += lowbit(j)) //将当前节点和它影响的所有父节点重置
{
//如果当前已经是负无穷了,那么后面的父节点要么没修改过,要么已经是负无穷,直接跳出
if(tr[j] == -INF) break;
tr[j] = -INF; //变回负无穷
}
}
}
void cdq(int l, int r)
{
if(l == r) return; //只有一个操作,不需要分治
int mid = l + r >> 1; //中间值
if(l <= mid) cdq(l, mid); //分治左区间
if(r > mid) cdq(mid + 1, r); //分治右区间
//只有让分治的区间 [l, r] 中存在添加和查询两种操作时,我们才需要处理左区间的添加操作对右区间的修改操作的影响(优化)
//[1, n] 之间都是添加操作,如果 r <= n,说明[l, r] 之间没有查询操作,不需要处理左区间对右区间的影响(不加这步优化会被卡常)
if(r > n)
{
int cnt = 0;
for(int i = l; i <= r; i++)
//将左区间的添加操作、右区间的查询操作取出来(用于处理左区间的添加操作对右区间的查询操作的影响)
if((i <= mid && a[i].z == 1) || (i > mid && a[i].z == 2))
b[++cnt] = a[i], b[cnt].z = i;
sort(b + 1, b + 1 + cnt); //区间中所有操作按横坐标从小到大排序
work(1, cnt + 1, 1, 1, 1), work(1, cnt + 1, 1, 1, -1); //左下(x + y)、左上(x + -y)
work(cnt, 0, -1, -1, 1), work(cnt, 0, -1, -1, -1); //右下(-x + y)、右上(-x + -y)
}
}
int main()
{
scanf("%d%d", &n, &m);
m += n;
for(int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].x, &a[i].y);
a[i].y++; //横坐标要对应树状数组,下标从1开始
a[i].z = 1; //所有初始状态作为添加操作插入
}
for(int i = n + 1; i <= m; i++)
{
scanf("%d%d%d", &a[i].z, &a[i].x, &a[i].y);
a[i].y++; //横坐标要对应树状数组,下标从1开始
}
for(int i = 1; i <= m; i++) maxy = max(maxy, a[i].y); //统计纵坐标的最大值,作为树状数组的长度
memset(tr, 0xcf, sizeof tr); //初始化为负无穷(取 max)
memset(res, 0x3f, sizeof res); //初始化为正无穷(取 min)
cdq(1, m); //CDQ分治
for(int i = 1; i <= m; i++)
if(a[i].z == 2) //输出查询操作的答案
printf("%d\n", res[i]);
return 0;
}
把sort改成归并也许会快?
效率提高不大吧,自带的sort效率也是很高的,这个其实不需要特别要求
归并:T(n)=2T(n/2)+O(n)=O(nlogn)
快排:T(n)=2T(n/2)+O(nlogn)=O(nlog2n)
不过树状数组也有O(nlogn)就是了
哦对,自带的sort好像是以快排为基础的,那的确归并快一些,我比较懒hh
stO Orz.