F - Permutation Distance
题意
给出一个排列 P。求序列D，\(D_i\)的定义如下。
\[D_{i}=\min_{j \neq i} \left\{\left|P_{i}-P_{j}\right|+|i-j|\right\} \]思路
在题目中遇到绝对值问题时，我们应该通过分类讨论来去掉绝对值，所以上式可以被拆成四个式子，如下：
\[1. D_i=(i-P_i)+\min\left\{P_j-j\right\} (P_i<P_j \ \&\& \ i>j) \\ \]\[2. D_i=(-i-P_i)+\min\left\{P_j+j\right\} (P_i<P_j \ \&\& \ i<j) \\ \]\[3. D_i=(P_i+i)+\min\left\{-P_j-j\right\} (P_i>P_j \ \&\& \ i>j) \\ \]\[4. D_i=(P_i-i)+\min\left\{-P_j+j\right\} (P_i>P_j \ \&\& \ i<j) \] 得到这个式子之后，那就是一个很裸的二维偏序维护问题。所以我们需要一共遍历四遍，用4个线段树来维护每个式子来更新答案。
对于 \(i > j\)，需要正序维护；反之倒序维护。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
int res[N], p[N];
struct SegmentTree{
struct Tree{
int l, r;
int mn;
}tr[N * 4];
void pushup(int u)
{
tr[u].mn = min(tr[u<<1].mn, tr[u<<1|1].mn);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r)
tr[u].mn = 1e9;
else
{
int mid = (l + r) >> 1;
build(u<<1, l, mid);
build(u<<1|1, mid + 1, r);
pushup(u);
}
}
void update(int u, int x, int t)
{// 单点修改，不需要懒标记
int l = tr[u].l, r = tr[u].r, mid = (l + r) >> 1;
if (l == r)
{
tr[u].mn = min(tr[u].mn, t);
}
else
{
if (x <= mid) update(u<<1, x, t);
else update(u<<1|1, x, t);
pushup(u);
}
}
int query(int u, int x, int y)
{// 查询区间[x, y]的最值
int l = tr[u].l, r = tr[u].r, mid = (l + r) >> 1;
if (x <= l && y >= r) return tr[u].mn;
else
{
int ans = 1e9;
if (x <= mid) ans = min(ans, query(u<<1, x, y));
if (y > mid) ans = min(ans, query(u<<1|1, x, y));
return ans;
}
}
}T1, T2;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> p[i];
memset(res, 0x3f, sizeof res);
T1.build(1, 1, n);
T2.build(1, 1, n);
for(int i = 1; i <= n; i ++)
{
res[i] = min(res[i], p[i] + i + T1.query(1, 1, p[i]));
res[i] = min(res[i], -p[i] + i + T2.query(1, p[i], n));
T1.update(1, p[i], -p[i] - i);
T2.update(1, p[i], p[i] - i);
}
T1.build(1, 1, n);
T2.build(1, 1, n);
for(int i = n; i >= 1; i --)
{
res[i] = min(res[i], p[i] - i + T1.query(1, 1, p[i]));
res[i] = min(res[i], -p[i] - i + T2.query(1, p[i], n));
T1.update(1, p[i], -p[i] + i);
T2.update(1, p[i], p[i] + i);
}
for(int i = 1; i <= n; i ++)
cout << res[i] << ' ';
cout << '\n';
}