「LAOI-4」石头

· · 题解

记 l_{x,0},l_{x,1},r_{x,0},r_{x,1} 分别为位置 x 左边第一个，左边第二个，右边第一个，右边第二个 >a_x 的数。

对于 (l,r),l<r，记 p 是区间 [l,r] 的最大值的位置，q 是区间 [l,r] 的次大值的位置。

假设最大值不位于端点即 l<p<r。

则从 l 到 r 需要的步数是 r-l_{p,0}，因为左边所有 <a_p 的数都会在 p 被染色前被染色。

那么对于 (l,r),l<p<r 是合法的区间，当且仅当 r-l_{p,0}=r_{p,0}-l 即 l-l_{p,0}=r_{p,0}-r。

综上对于区间最大值为 a_p 且最大值不位于端点的合法区间数是 \min(p-l_{p,0}-1,r_{p,0}-p-1)，即端点取满左边或右边。

枚举 p 即可算出全部贡献。

当最大值位于一个端点，假设位于 l。

此时 l=p=l_{q,0}，因为 a_p 是最大值所以 a_p>a_q，因为 a_q 是次大值，所以 p 是左边第一个 >a_q 的位置。

同时 l 到 r 的步数变为了 r-l_{q,1}，因为 p 一开始就被染色所以左边只有 <q 的才会被染色。

此时则要求 p-l_{q,1}=r_{p,0}-r 即 r=r_{p,0}-(p-l_{q,1})，判断 r 的位置在 [q,r_{q,0}) 中才能保证区间次大值为 q。

枚举 q 即可算出全部贡献。

还要算上 l=r 的情况，可以最后单独加，也可以直接在第一部分中计算上。

所以计算贡献的时间复杂度是 O(n) 的。

问题转化成求每个位置 x 左边第一个，左边第二个，右边第一个，右边第二个 >a_x 的数。可以使用链表。

具体的，从小到大删去数，在删去之前从链表上找所在位置的前驱，前驱的前驱，后继，后继的后继即可。

所以总时间复杂度是 O(n) 的。

int main()
{
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>s;srand_(s,n);
    u[0]=0,v[0]=1,u[n+1]=n,v[n+1]=n+1;//初始化链表
    for(int i=1;i<=n;++i)
        b[a[i]]=i,u[i]=i-1,v[i]=i+1;
    for(int i=1;i<=n;++i)
    {
        int cur=b[i];//找到 i 对应的位置
        l[cur][0]=u[cur],l[cur][1]=u[u[cur]];
        r[cur][0]=v[cur],r[cur][1]=v[v[cur]];
        //下面计算第一部分，同时加上了 l=r 的情况
        ans+=min(r[cur][0]-cur,cur-l[cur][0]);
        u[v[cur]]=u[cur],v[u[cur]]=v[cur];
    }
    for(int q=1,p,cur;q<=n;++q)//计算第二部分
    {
        p=l[q][0],cur=r[p][0]-(p-l[q][1]);
        if(cur>=q&&cur<r[q][0]) ++ans;
        p=r[q][0],cur=l[p][0]+(r[q][1]-p);
        if(cur>l[q][0]&&cur<=q) ++ans;
    }
    cout<<ans<<'\n';return 0;
}