abc283 F - Permutation Distance

标签：Distance min int void Permutation tr ans INF abc283

题意：

给定 \(1\sim n\) 的排列 \(P\)，对每个 \(i\in [1,n]\)，计算 \(\min\limits _{j\neq i}\{ |P_i-P_j|+|i-j| \}\)

\(n\le 2e5\)

思路：

我超，俩绝对值怎么办？硬拆就完事了！

\[i>j,Pi>Pj\implies i+Pi+min\{-j-Pj\}\\ i>j,Pi<Pj\implies i-Pi+min\{-j+Pj\}\\ i<j,Pi>Pj\implies -i+Pi+min\{j-Pj\}\\ i<j,Pi<Pj\implies -i-Pi+min\{j+Pj\} \]

经典二位偏序，树状数组或者线段树维护最值，做四次

const signed N = 2e5 + 5, INF = 1e9;
int n, a[N], ans[N];

int tr[N * 4];
void init() {
    fill(tr, tr + N * 4, INF);
}
void modify(int u, int l, int r, int p, int x) { //单点修改
    if(l == r) return tr[u] = x, void();
    int mid = (l + r) / 2;
    if(p <= mid) modify(u * 2, l, mid, p, x);
    else modify(u * 2 + 1, mid + 1, r, p, x);
    tr[u] = min(tr[u * 2], tr[u * 2 + 1]);
}
int ask(int u, int l, int r, int x, int y) {
    if(x > y) return INF;
    if(x <= l && r <= y) return tr[u];
    int mid = (l + r) / 2, s = INF;
    if(x <= mid) s = min(s, ask(u * 2, l, mid, x, y));
    if(y > mid) s = min(s, ask(u * 2 + 1, mid + 1, r, x, y));
    return s;
}

void sol() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    fill(ans, ans + N, INF);
    
    init(); for(int i = 1; i <= n; i++) {
        ans[i] = min(ans[i], i + a[i] + ask(1, 1, n, 1, a[i] - 1));
        modify(1, 1, n, a[i], -i - a[i]);
    }
    init(); for(int i = 1; i <= n; i++) {
        ans[i] = min(ans[i], i - a[i] + ask(1, 1, n, a[i] + 1, n));
        modify(1, 1, n, a[i], -i + a[i]);
    }
    init(); for(int i = n; i >= 1; i--) {
        ans[i] = min(ans[i], -i + a[i] + ask(1, 1, n, 1, a[i] - 1));
        modify(1, 1, n, a[i], i - a[i]);
    }
    init(); for(int i = n; i >= 1; i--) {
        ans[i] = min(ans[i], -i - a[i] + ask(1, 1, n, a[i] + 1, n));
        modify(1, 1, n, a[i], i + a[i]);
    }
    
    for(int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
}

标签：Distance,min,int,void,Permutation,tr,ans,INF,abc283
From： https://www.cnblogs.com/wushansinger/p/17021389.html