CF1539F Strange Array 题解

题意：

\(\texttt{Vasya}\) 有一个长度为 \(n\) 的数组 \(a\)。

对于每一个元素 \(a_i\)，进行一次以下操作，可以获得的最大值称为 \(a_i\) 的奇异值：

选取一对 \(l,r\) 使得 \(1\le l\le i\le r\le n\)。

将区间 \([l,r]\) 中的元素从小到大排序，如果有相同元素，则可以任意排列它们的位置。

记 \(a_i\) 现在的位置为 \(x\)，定义序列中心 \(y\) 为 \(\lceil\frac{l+r}{2}\rceil\)，则距离为 \(|x-y|\)。

请你帮助 \(\texttt{Vasya}\) 求出每一个元素的奇异值，注意每个元素之间互不影响。

数据范围：

\(1\le n\le 2\times 10^5,~1\le a_i\le n\) 。

~~好像是套路题，但我不知道~~。考虑区间已经确定且 \(a_i\) 升序排序后如何求距离 \(\rm dis\) 。

记 \(a_{\rm mid}\) 为中位数，\(a_x\) 为排序后的下标，\(a_l,\,a_m,\,a_r\) 为大于、等于和小于 \(a_x\) 的数的个数

考虑 \(a_x > a_{\rm mid}\) 的情况，如下

那么 \(\mathrm{dis} = \frac{a_l+a_m+a_r}{2}-a_r=\left\lfloor\frac{a_l+a_m-a_r}{2}\right\rfloor\) 。同理 \(a_x > a_{\rm mid}\) 时为 \(\left\lfloor\frac{a_r+a_m-a_l+1}{2}\right\rfloor\) 。

有意思的是，这个东西和 \(a_x\) 的位置无关。换言之，我们只需要求出 \(a_l,\,a_m,\,a_r\) 即可。

令 \(b_i =[a_i \le a_x] - [a_i > a_x]\) ，即小于等于的数为 \(1\) ，大于的为 \(-1\) ，那么 \[ \left(\sum_{i=l}^rb_i\right) -1 = (a_l + a_m)\times 1 + a_r \times (-1) = 2\times \mathrm{dis} \] 这里减 \(1\) 是去掉 \(a_x\) ，那么 \(\mathrm{dis} = \frac{\sum_{i=l}^r b_i-1}{2}\) 。

于是我们只需要求出 \(\sum_{i=l}^r b_i\) ，考虑把它拆成 \(\sum_{i=l}^x b_i + \sum_{i=x}^r b_i-1\)

这个东西就是 \([1,x]\) 的最大后缀和加上 \([x,n]\) 的最大前缀和，考虑线段树维护即可。

对于 \(a_x < a_{\rm mid}\) 的情况，我们可以直接令 \(a_x \gets (-a_x)\) ，这样只需要稍微改改就可以了。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n, ans[N];
struct arr { int x, id; } a[N];
struct node { int pre, suf, sum; } tr[N * 4];
void push_up(int at)
{
    tr[at].sum = tr[ls(at)].sum + tr[rs(at)].sum;
    tr[at].pre = max(tr[ls(at)].pre, tr[ls(at)].sum + tr[rs(at)].pre);
    tr[at].suf = max(tr[rs(at)].suf, tr[rs(at)].sum + tr[ls(at)].suf);
}
void build(int at = 1, int l = 1, int r = n)
{
    if(l == r) return tr[at] = {-1, -1, -1}, void(0);
    const int mid = (l + r) >> 1;
    build(ls(at), l, mid); build(rs(at), mid + 1, r); push_up(at);
}
void modify(int x, int v, int at = 1, int l = 1, int r = n)
{
    if(l == r) return tr[at] = {v, v, v}, void(0);
    const int mid = (l + r) >> 1;
    x <= mid ? modify(x, v, ls(at), l, mid) : modify(x, v, rs(at), mid + 1, r); push_up(at);
}
node qry(int nl, int nr, int at = 1, int l = 1, int r = n)
{
    if(nl > r || nr < l) return {0, 0, 0};
    if(nl <= l && r <= nr) return tr[at];
    const int mid = (l + r) >> 1;
    const node x = qry(nl, nr, ls(at), l, mid), y = qry(nl, nr, rs(at), mid + 1, r);
    return {max(x.pre, x.sum + y.pre), max(y.suf, y.sum + x.suf), x.sum + y.sum};
}
void solve(int type)
{
    build();
    rep(i, 1, n)
    {
        int j = i; while(j < n && a[j + 1].x == a[i].x) ++j;
        rep(k, i, j) modify(a[k].id, 1);
        rep(k, i, j)
        {
            const node x = qry(1, a[k].id), y = qry(a[k].id, n);
            up(ans[a[k].id], x.suf + y.pre - 1 - (!type));
        }
        i = j;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; rep(i, 1, n) { cin >> a[i].x, a[i].id = i; }
    sort(a + 1, a + 1 + n, [](arr a, arr b) { return a.x < b.x; });
    solve(0);
    rep(i, 1, n / 2) swap(a[i], a[n - i + 1]);
    rep(i, 1, n) a[i].x = -a[i].x;
    solve(1);
    rep(i, 1, n) cout << ans[i] / 2 << " \n"[i == n];
    return 0;
}