题解：P10407 「SMOI-R1」Game

· · 题解

就我觉得 T3 比 T4 简单吗QAQ

首先有一个非常常规的思路：枚举每一个数，求出其作为最大值的区间个数。这道题也是如此。

如果最终的序列 a 长度够小，那么我们可以利用单调栈得出每一个数 a_i 向前和向后的第一个 >a_i 的数 a_{l_i} 和 a_{r_i}，如果找不到则分别为 0,|a|+1，那么 a_i 作为最大值的区间就有 (i-l_i)(r_i-i) 个。

但是需要注意，有的区间是会被算重的，比如 a=\{1,2,1,2\}，两个 2 分别计算得到的区间都包含 [2,4],[1,4]。这个时候考虑更改 l_i 的定义为向前找到的第一个 ≥a_i 的数的下标，如果找不到则为 |a|+1，计算方式仍然是 (i-l_i)(r_i-i)。这样就可以保证不会重复计算了，原因显然，因此把它当成一个 Trick 掌握就行了。

但是出题人非常可爱啊！这个 a 的长度可以达到 10^{15}，不可能直接计算。但是 n 的范围倒是很合理。这就说明我们要找到 a 序列的计算规律。

我们将 a 视为 n 个形如 \{1,2,\dots,b_i-1,b_i\} 的子段前后拼接得到的序列，记 s_{i,j} 表示第 i 个子段中的第 j 个数在 a 中的下标。

先考虑 s_{i,b_i} 的代价该怎么计算。由于各个子段的单调性，我们可以知道其向前能够找到的第一个 ≥b_i 的数的下标一定是 s_{j,b_j}（j<i），向后能够找到的第一个 > b_i 的数的下标一定是 s_{k,b_i+1}（i<k，注意是 b_i 而不是 b_k）。可以发现 b_j 是 b_i 向前第一个大于等于它的数，b_k 是 b_i 向后第一个大于它的数。可以通过这个结论，利用单调栈找到 j,k。我们找到这两个 j,k 记为 L(i),R(i)（如果不存在满足条件的 j 或 k，则分别变为 0,n+1），则 s_{i,b_i} 的区间个数就是 (s_{i,b_i}-s_{L(i),b_{L(i)}})(s_{R(i),b_{i}+1}-s_{i,b_i})，可以利用 b_i 的前缀和解决。

我们记 sum_i=\sum _{j=1}^ib_j，那么：

(s_{i,b_i}-s_{L(i),b_{L(i)}})(s_{R(i),b_{i}+1}-s_{i,b_i})=(sum_i-sum_{L(i)})(sum_{R(i)-1}-sum_i+1+[R(i)\leq n])

每一个子段的顶点值我们就算完了，我们考虑将这种做法拓展到其它数上面。其实我们可以利用图像去思考：

我们知道对于每一个数，要去找前面和后面比自己大的，由于除了顶点以外，每个数的后面都有一个比自己大一的数，所以右侧比较好找。而对于左侧，我们结合上图去思考，不难发现最终形成的 a 序列就是若干个等腰直角三角形排在一起，那么每个数作为最大值的区间可以延展到的左端点一定是在 s_{k,b_k} 的位置。因此我们像之前那样用一个单调栈就行了。

但是对于每个数都用单调栈的话显然会寄。

我们可以找一下规律：

考虑对第 3 个子段的每个元素的答案进行统计，我们发现 IK 这一段对应过去的线段是 EF，这说明 1\leq j\leq |IK| 的元素 s_{3,j} 可以向左延伸的最远点都是 F，即 s_{2,b_2}。而 GL 对应过去是 CD 的一个子线段，这说明 |IK|<j\leq |GH| 的元素 s_{3,j} 向左延伸的最远点都是 s_{1,b_1}。这启示我们将每一个子段中的元素分成若干个子部分进行处理，并且要保证每个部分的 s_{i,j} 对应的左侧端点是相同的。

于是我们用单调栈去储存 b_i，维护一个单调递减的子序列的下标。当我们要处理第 i 个子段时，我们就在栈中从后往前遍历，设当前遍历的元素为 p，上一个遍历的元素是 q，那么我们就将 [s_{i,b_q+1},s_{i,b_p}] 的答案进行加和，下文令 t=sum_{i-1}-sum_p+b_q，m=b_p-b_q，则：

\begin{aligned} \sum _{j=b_q+1}^{b_p}j(s_{i,j}-s_{p,b_p})&=\sum _{j=b_q+1}^{b_p}j(sum_{i-1}-sum_p+j)\\ &=\sum _{j=1}^{m}(b_q+j)(sum_{i-1}-sum_p+b_q+j)\\ &=mb_qt+\dfrac{m(b_q+t)(m+1)}{2}+\dfrac{m(m+1)(2m+1)}{6} \end{aligned}

这样就可以 O(1) 计算这一段的答案之和了。

根据单调栈的性质，可以推断 n 个子段分成的子部分的个数和是 O(n) 级别的，可以跑过。

最后就是一些细节问题了，放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+5;
const int MOD=998244353;
int n,a[MAXN];
stack<int> stk;
int res;
int L[MAXN],R[MAXN];
int sum[MAXN];
int qpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%MOD;
        x=1ll*x*x%MOD;
        y>>=1;
    }
    return res;
}
int solve(int x,int y,int z){ return (1ll*x*y%MOD*z%MOD+1ll*(x+y)%MOD*(1ll*(z+1)*z/2%MOD)%MOD+1ll*z*(z+1)%MOD*(2*z+1)%MOD*qpow(6,MOD-2)%MOD)%MOD; }
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i],sum[i]=sum[i-1]+a[i],sum[i]%=MOD;
    a[n+1]=a[n];
    for(int i=1;i<=n;i++)
    {
        while(!stk.empty()&&a[stk.top()]<a[i])  R[stk.top()]=i,stk.pop();
        if(!stk.empty())    L[i]=stk.top();
        stk.push(i);
    }
    while(!stk.empty()) R[stk.top()]=n+1,stk.pop();
    for(int i=1;i<=n;i++)   res+=1ll*a[i]*(sum[i]-sum[L[i]]+MOD)%MOD*(sum[R[i]-1]-sum[i]+1+(R[i]<=n)*a[i]+MOD)%MOD,res%=MOD;
    while(!stk.empty()) stk.pop();
    stk.push(0),a[0]=1e9;
    for(int i=1;i<=n;i++)
    {
        int lst=0;
        while(!stk.empty()&&a[stk.top()]<=a[i]-1)   res+=solve(sum[i-1]-sum[stk.top()]+lst,lst,a[stk.top()]-lst),lst=a[stk.top()],stk.pop();
        if(lst!=a[i]-1) res+=solve(sum[i-1]-sum[stk.top()]+lst,lst,a[i]-lst-1),res%=MOD;
        while(!stk.empty()&&a[stk.top()]==a[i]) stk.pop();
        stk.push(i);
    }
    cout<<res;
    return 0;
}