题解 P9461

· · 题解

Solution

考虑到一个事实：区间最小众数只能为 1 或者区间的第一个数 l。

证明：不难发现子区间可以写成 [l,a_x],[1,a_{x+1}],[1,a_{x+2}],\cdots,[1,a_{y-1}],[1,r]。

如果最小众数 x 在 [2,l) 之间，此时每个 x 的左边都存在一个该段的 1，因此 1 的出现次数一定不小于它，因此 x 不是最小众数。

如果最小众数 x 比 l 更大，此时每个 x 的左边都存在一个该段的 l，因此 l 的出现次数一定不小于它，因此 x 不是最小众数。

进一步发现 l 是区间众数当且仅当每段右端点都 \geq l。

考虑对于 l=2,3,\cdots,\max\{a\} 分别计算左端点为 l 且最小众数为 l 的区间数量，用总区间数 \frac{n(n+1)}{2} 减去即可得到最小众数为 1 的区间数量。

对于每个 l 尝试归纳其充分必要的合法条件：从第 x 段的 l 走到第 y 段的 r 合法当且仅当对于 i\in [x,y] 都满足 a_i\geq l。因此使用链表维护每个极长的 \geq l 段并更新答案即可。

时间复杂度 O(n+\max\{a\})，可以通过离散化做到 O(n\log n)。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=998244353,inv=(p+1)>>1,N=1e6;
vector<int> v[1000003];
int a[1000003],f[1000003],g[1000003];
int l[1000003],r[1000003];
signed main()
{
    int n=read(),ans=0,sf=0,sg=0,s=0;
    for(int i=1,x; i<=n; ++i)
        x=read(),s=(s+x)%p,v[x].push_back(i);
    s=1ll*s*(s+1)%p*inv%p;
    for(int i=N; i>1; --i)
    {
        for(int j:v[i])
        {
            l[j]=r[j]=j,f[j]=i,g[j]=1,
            sf=(sf+i)%p,sg=(sg+1)%p;
            if(l[j-1])
            {
                int x=l[j-1],len=j-x;
                sf=(sf+1ll*len*f[j])%p,
                sg=(sg+1ll*len*g[j])%p,
                r[x]=j,l[j]=x,
                f[x]=(f[x]+f[j])%p,
                g[x]=(g[x]+g[j])%p;
            }
            if(r[j+1])
            {
                int x=l[j],len=j+1-x;
                sf=(sf+1ll*len*f[j+1])%p,
                sg=(sg+1ll*len*g[j+1])%p,
                r[x]=r[j+1],l[r[j+1]]=x,
                f[x]=(f[x]+f[j+1])%p,
                g[x]=(g[x]+g[j+1])%p;
            }
        }
        int t=(sf+p-1ll*sg*(i-1)%p)%p;
        ans=(ans+1ll*t*i)%p,s=(s+p-t)%p;
    }
    ans=(ans+s)%p,  printf("%d\n",ans);
    return 0;
}