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;
}