题目链接：ABC283_F (opens new window)

题目大意：

给定一个长度为 的排列 ，对每一个 求解

思路：

看到两个绝对值，我们不妨将绝对值拆除，分为四种情况来讨论。

1. ，
   
2. ，
   
3. ，
   
4. ，
   

我们先考虑 的两种情况:

• 如果 ，我们可以给 建立权值树状数组， 节点赋值为 。
  我们从小到大遍历 i，可以保证之前出现过的项中 j 一定小于 i，然后遍历的过程中更新树状数组，如果我们用树状数组求 的前缀最大值，如此一来一定可以保证得到的最大值满足
• 如果 我们与第一种情况处理方式类似，但是有一点不同的是我们此时要找到的是大于 的 ，因此此时应该在树状数组求 的后缀最大值。一种可行的方案是我们求前缀值的函数由从大到小遍历改为从小到大遍历。另一种更好的方法是，我们将树状数组下标 映射成 ，也就是相当于将树状数组整体反转了一下，如此一来我们求解后缀最大值就转化成了求解前缀最大值。因此我们再建立一个树状数组对这种情况特殊处理，对于 我们将节点 赋值为 即可。

而 的情况也是类似，只需要改变 i 的遍历顺序为从大到小就可以了。

Code：

#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick {
    std::vector<T> a;
    int n;
    
    Fenwick(int n = 0) {
        init(n);
    }
    
    void init(int n) {    
        this->n = n;
        a.assign(n, T()); 
    }

    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    
    T get(int x) {
        T ans = T();
        for (int i = x; i >= 1; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return get(r) - get(l - 1);
    }

    int kth(T k) {
        int x = 0;
        for (int i = 1 << (31 - __builtin_clz(n)); i >= 1; i >>= 1) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};

const int inf = 1e9;

struct Max {
    int v;
    Max(int x = -inf) : v(x) {};
    Max &operator+=(const Max &rhs) {
        v = std::max(v, rhs.v);
        return *this;
    }
};

int main() {	
	std::ios::sync_with_stdio(false); 
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	std::vector<int> p(n);
	for (int i = 0; i < n; i++) {
		std::cin >> p[i];
		p[i]--;
	}

	Fenwick<Max> f1(n + 1), f2(n + 1);

	std::vector<int> res(n);
	for (int i = 0; i < n; i++) { 
		res[i] = std::min(p[i] + i - f1.get(p[i] + 1).v, i - p[i] - f2.get(n - p[i]).v);
		f1.add(p[i], p[i] + i);
		f2.add(n - 1 - p[i], i - p[i]);
	}

	f1.init(n);
	f2.init(n);

	for (int i = n - 1; i >= 0; i--) { 
		res[i] = std::min({res[i], p[i] - i - f1.get(p[i] + 1).v, -p[i] - i - f2.get(n - p[i]).v});
		f1.add(p[i], p[i] - i);
		f2.add(n - 1 - p[i], -p[i] - i);
	}

	for (int i = 0; i < n; i++) {
		std::cout << res[i] << " \n"[i == n - 1];
	}

	return 0;
}	

// Make sure to add code blocks to your code group