CF1539F Strange Array

· · 题解

题意：给定一个序列，需要求出序列中每个元素的奇怪值。a_i 的奇怪值定义为选取任意一个区间，将区间里的数升序排序后 a_i 的新位置和该区间中位数下标距离的最大值。(若区间长度为偶数，中位数的下标为 \frac{l+r+1}{2} )。

首先考虑如果区间已经确定，且已经升序排序后如何求距离。

令 a_{mid} 表示中位数， a_x 表示排序后的新下标，a_l,a_m,a_r 表示 \le a_x,=a_x,>a_x 的数的个数。下图是 a_x > a_{mid} 的情况。

显然 dis=\frac{a_l+a_m+a_r}{2}-a_r=\lfloor\frac{a_l+a_m-a_r}{2}\rfloor .

同理若 a_x<a_{mid} ，则有 dis=\lfloor \frac{a_r+a_m-a_l+1}{2} \rfloor .

也就是说只要知道 a_l,a_m,a_r ，无需排序也能确定距离。接下来就是中位数的老套路了：

新开一个数组 b ,将 \le a_x 的数的位置赋值为1 ，>a_x 的数的位置赋值为 -1 。那么 \sum^{r} _ {i=l} b_i-1=(a_l+a_m)\times 1 + (a_r)\times (-1)=dis\times2 ，前面减1是要除去 a_x 本身。即 dis=\frac{\sum^{r} _ {i=l} b_i-1}{2} 。

接下来考虑求 \sum^{r} _ {i=l} b_i ，拆成两份也就是 \sum_{i=l}^{x}b_i+\sum_{i=x}^{r}b_i-1 ，然后发现 \sum_{i=l}^{x}b_i 就是维护整个 1\sim x 的最大后缀，\sum_{i=x}^{r}b_i 就是维护整个 x\sim n 的最大前缀。

所以只用套区间合并线段树的模板就好。

另外，对于另一种 a_x<a_{mid} 的情况还有一种取巧的方法：只用把 a 数组整个翻转再把每个元素变为相反数就变成 a_x<a_{mid} 的情况了。

#include<bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define re register int
#define inf 0x7fffffffffffffff
#define Pair pair<int,int>
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f==1?x:-x;
}
const int N=2e5+10;
struct Seg{
    int l,r,lm,rm,sum;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define lm(x) tree[x].lm
    #define rm(x) tree[x].rm
    #define sum(x) tree[x].sum
}tree[N<<2];
inline void pushup(int p)
{
    sum(p)=sum(p<<1)+sum(p<<1|1);
    lm(p)=max(lm(p<<1),sum(p<<1)+lm(p<<1|1));
    rm(p)=max(rm(p<<1|1),sum(p<<1|1)+rm(p<<1));
}
void build(int p,int l,int r)
{
    l(p)=l;r(p)=r;
    if(l==r)return sum(p)=lm(p)=rm(p)=-1,void();
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void change(int p,int pos,int x)
{
    if(l(p)==r(p))return sum(p)=lm(p)=rm(p)=x,void();
    int mid=(l(p)+r(p))>>1;
    if(pos<=mid)change(p<<1,pos,x);
    else change(p<<1|1,pos,x);
    pushup(p);
}
Seg query(int p,int l,int r)
{
    if(r(p)<l || r<l(p))return {0,0,0,0,0};
    if(l<=l(p) && r>=r(p))return tree[p];
    Seg a=query(p<<1,l,r),b=query(p<<1|1,l,r);
    return {min(a.l,b.l),max(a.r,b.r),max(a.lm,a.sum+b.lm),max(b.rm,b.sum+a.rm),a.sum+b.sum};
}
int n,ans[N];
struct node{int x,id;}a[N];
bool cmp(node a,node b){return a.x<b.x;}
void calc(int flag)
{
    build(1,1,n);
    for(re i=1;i<=n;++i)
    {
        int j=i;
        while(j<n && a[j+1].x==a[i].x)++j;
        for(re k=i;k<=j;++k) change(1,a[k].id,1);
        for(re k=i;k<=j;++k)
        {
            Seg p=query(1,1,a[k].id),q=query(1,a[k].id,n);
            ans[a[k].id]=max(ans[a[k].id],p.rm+q.lm-1-!flag);
        }
        i=j;
    }
}
signed main()
{
    n=read();
    for(re i=1;i<=n;++i)
        a[i].x=read(),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    calc(0);
    for(re i=1;i<=n/2;++i) swap(a[i],a[n-i+1]);
    for(re i=1;i<=n;++i) a[i].x=-a[i].x;
    calc(1);
    for(re i=1;i<=n;++i) 
        printf("%lld ",ans[i]/2);
    return 0;
}