题解 CF1693E【Outermost Maximums】

周子衡 · 2022-07-01 16:32:32 · 题解

我们先考虑暴力模拟整个过程。考虑每次如何决定是调最左的最大值还是最右的最大值。一个直观的想法是，假设最左的最大值左侧的最大元素为 \mathrm{maxl}，最右的最大值右侧的最大元素为 \mathrm{maxr}，我们一定选 \mathrm{maxl,maxr} 中较小的那一侧操作。正确性显然。但直接模拟的话，最坏情况下步数就已经是 O(n^2) 级别了，我们无法承受。

我们来转换一下视角。对每个 i\in [1,n]，我们来看看 a_i 变到 0 需要多少次操作。可以发现，数列中比 a_i 值还大的元素是不重要的，我们只关心小于 a_i 的元素。我们把这些值按顺序排列在一条数轴上。对每个值，如果它只在 i 左侧出现，我们就染成白色；只在右侧出现就染成黑色；如果在两侧都出现，就染成黄色。下面是一个例子。

可以发现，整个操作过程中，每次减小 a_i，都是把 a_i 变成数轴上当前 a_i 左侧的白位置中最大的那一个，或者变成数轴上当前 a_i 左侧的黑位置中最大的那一个。注意：黄位置既是黑位置又是白位置（这意味着 a_i 必须经过所有黄位置）。直接模拟的话时间复杂度仍为 O(n^2)。注意到相邻两个 i 之间至多有 O(1) 个位置的颜色发生变化，我们需要维护一个支持单点修改、查询前缀信息的数据结构，下面以线段树为例。我们需要提取原序列的一些信息，来快速计算步数。

我们先不考虑黄位置，来集中精力解决黑白位置步数的计算。可以发现，我们每次会跳到下一个同色连续段的末尾，因而大部分情况下我们会经过每个同色连续段。有一个例外情况：如果某个同色连续段长度只有 1，我们跳到该连续段末尾也就相当于跳到了该连续段开头，那么我们实际上会跳过这个连续段左边的连续段，也就使得步数少了 1。那是不是步数就是长度大于等于 2 的连续段数量呢？也不尽然。如果很多长度为 1 的连续段相邻，那么我们会一路猛跳，实际上步数只会减少这个“黑白黑白”段总长的一半（向上取整）。也就是说，我们不仅要维护同色连续段，还需要去维护黑白黑白的连续段。

最后来考虑黄色位置。由于黄色位置都是必须到达的，我们可以先在答案里预先加上黄色位置的数量。注意到每个黄色位置的下一个黑白连续段是可以跳过的，我们又要减去黄色位置的数量（这一步和上一步加起来相当于啥都没做）。例外有三个：如果两个黄色相邻，那么后一个黄色的减 1 实际上不应该减，得加回去；如果黄色前面紧邻一个长度为 1 的白 / 黑色连续段，那么这个连续段又要被跳过去了，可以认为它是“没有活性”的；如果某个长为 1 的白 / 黑色连续段的前面是黄色，那它也丧失了“跳过”的能力，也说它是没有活性的。注意这里活性只针对长度为 1 的连续段而言。也就是说，我们要对上一段中的算法稍作修改，只维护有活性的极长连续段的长度。

由于这个做法细节比较多，这里单独讲讲实现细节。对线段树上的每个区间，我们维护左右端点的颜色（用来判断连续段数）；整个区间是否是黑白黑白的交替；如果不是的话，左边的黑白黑白最长延伸的长度，右边的黑白黑白最长延伸的长度。合并两个区间的时候，如果两个区间中都不是全黑白交替，那么我们就处理中间形成的黑白交替段（也就是把长度除以 2 上取整从答案中减去）。这样每个黑白交替段都在它“成型”的时候被算到答案里去了。细节可以参考下面代码里的 merge 函数。

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct dat
{
    int ans;bool full;
    int lc,rc,llen,rlen;
};

dat merge(dat L,dat R)
{
    dat X;X.ans=L.ans+R.ans;
    if(L.rc==R.lc&&L.rc!=2)X.ans--;
    if(R.lc==2&&L.rc!=2)X.ans--;

    X.full=L.full&&R.full&&(L.rc!=R.lc);
    X.lc=L.lc,X.rc=R.rc;
    if(X.full){X.llen=X.rlen=L.llen+R.llen;return X;}

    if(L.full&&R.full)
    {
        X.llen=L.llen-1,X.rlen=R.rlen-1;return X;
    }
    if(L.full)
    {
        X.rlen=R.rlen;
        if(R.lc==(L.rc^1))X.llen=L.llen+R.llen;
        else
        {
            X.llen=max(L.llen-1,0);
            X.ans-=R.llen/2;
        }
        return X;
    }
    if(R.full)
    {
        X.llen=L.llen;
        if(R.lc==(L.rc^1))X.rlen=R.rlen+L.rlen;
        else
        {
            X.rlen=max(R.rlen-1,0);
            X.ans-=L.rlen/2;
        }
        return X;
    }

    X.llen=L.llen,X.rlen=R.rlen;
    if(R.lc==(L.rc^1))X.ans-=(L.rlen+R.llen+1)/2;
    else
    {
        X.ans-=L.rlen/2,X.ans-=R.llen/2;
    }
    return X;
}
dat F[3];
void init_F()
{
    F[0].ans=F[1].ans=F[2].ans=1;
    F[0].full=F[1].full=1,F[2].full=0;
    F[0].llen=F[1].llen=F[0].rlen=F[1].rlen=1,F[2].llen=F[2].rlen=0;
    for(int i=0;i<3;i++)F[i].lc=F[i].rc=i;
}
struct SegmentTree
{
    struct nd
    {
        int l,r;
        dat D;
    }t[1000000];
    void upd(int k){t[k].D=merge(t[k<<1].D,t[k<<1|1].D);}
    void build(int l,int r,int k=1)
    {
        t[k].l=l,t[k].r=r;if(l==r){t[k].D=F[2];return;}
        int mid=(l+r)>>1;build(l,mid,k<<1),build(mid+1,r,k<<1|1);upd(k);
    }
    void update(int x,int v,int k=1)
    {
        if(t[k].l==t[k].r){t[k].D=F[v];return;}
        int mid=(t[k].l+t[k].r)>>1;if(x<=mid)update(x,v,k<<1);else update(x,v,k<<1|1);
        upd(k);
    }
    dat query(int l,int r,int k=1)
    {
        if(l<=t[k].l&&t[k].r<=r)return t[k].D;
        int mid=(t[k].l+t[k].r)>>1;
        if(r<=mid)return query(l,r,k<<1);if(l>mid)return query(l,r,k<<1|1);
        return merge(query(l,r,k<<1),query(l,r,k<<1|1));
    }
}T;

int a[300000];bool vis[300000],is_lst[300000];
vector<int> all;

int main()
{
    init_F();
    int n=0;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),all.push_back(a[i]);
    all.push_back(0);
    sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());
    for(int i=1;i<=n;i++)a[i]=lower_bound(all.begin(),all.end(),a[i])-all.begin();

    T.build(0,n);T.update(0,2);for(int i=1;i<=n;i++)T.update(i,1);

    vis[0]=1;for(int i=n;i>=1;i--)if(!vis[a[i]])vis[a[i]]=1,is_lst[i]=1;

    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        T.update(a[i],2);
        ans+=T.query(0,a[i]).ans-1;
        if(is_lst[i])T.update(a[i],0);
    }
    printf("%lld",ans);
}