自动搬运

查看原文

来自洛谷，原作者为

	int_R 我在衡水上高三没空想你

搬运于2025-08-24 22:57:18，当前版本为作者最后更新于2024-03-15 15:50:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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