题解：P10407 「SMOI-R1」Game

Mengguigui · 2026-08-08 15:35:17 · 题解

解题思路

Subtask 1：n \le 10^2，b_i \le 10^2

把序列展开，暴力。

时间复杂度为 O((\sum_{i=1}^n b_i)^2)。

Subtask 2：n \le 10^4，b_i \le 10^2

猜测时间复杂度为 O(n^2)，枚举左右端点所在的段 l, r。

当 l, r 在同一个段中时

考虑用平方和级数公式 O(1) 求。

当 l, r 在不同段中时

不妨设 l 在第 i 段，r 在第 j 段。

令 W = \max_{k=i}^{j-1} b_k，则最大值显然为 \max(W, r)。

注意到 \sum_{r=1}^{b_j}\max(W, r) 与 l 的取值无关。

同样可以 O(1) 求。

Subtask 3：n \le 10^6，b_i \le 10^9，b_1 \le b_2 \le \dots \le b_n

考虑不同段。

此时 W = b_j。

则 \sum_{l=1}^{b_i}\sum_{r=1}^{b_j}\max(b_{j-1}, r)

复杂度 O(n)。

Subtask 4：n \le 10^6，b_i \le 10^9

没有单调性，考虑人造单调性（单调队列，单调栈）。

维护一个单调递减栈，在这个过程中，弹出的都是小于等于 b_i 的，把弹出的长度合并到 b_i 中，没弹出的大于 b_i。

复杂度 O(n)，具体实现可以看代码。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=998244353;
const ll INV2=(MOD+1)/2;
const ll INV6=166374059;
struct Node
{
    // 真实的最大值，用于和新的 b[i] 比较
    ll mx;
    // 所有拥有这个最大值的起始块，其 b[i] 之和
    // 只需要保存模 MOD 后的结果
    ll w;
};
// 计算 1+2+...+x
ll sum1(ll x)
{
    x%=MOD;
    return x*((x+1)%MOD)%MOD*INV2%MOD;
}
// 计算 1^2+2^2+...+x^2
ll sum2(ll x)
{
    ll a=x%MOD;
    ll b=(x+1)%MOD;
    ll c=(2*(x%MOD)+1)%MOD;
    return a*b%MOD*c%MOD*INV6%MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<Node> stk(n);
    ll ans=0;
    /*
        当前栈内所有元素的sumWM=Σ w*mx
        它用于计算 mx>当前x的所有组的贡献。
    */
    ll sumWM=0;
    for(int i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        ll xm=x%MOD;
        // 1.左右端点都位于当前块中的区间
        ans=(ans+sum2(x))%MOD;
        /*
            弹出的都是 mx<=x 的组
            lowW=Σ w
            lowQ=Σ w*mx*(mx-1)
        */
        ll lowW=0;
        ll lowQ=0;
        while(!stk.empty()&&stk.back().mx<=x)
        {
            ll mx=stk.back().mx;
            ll w=stk.back().w;
            stk.pop_back();
            ll mm=mx%MOD;
            lowW+=w;
            if(lowW>=MOD)lowW-=MOD;
            ll q=w*mm%MOD;
            q=q*((mm-1+MOD)%MOD)%MOD;
            lowQ+=q;
            if(lowQ>=MOD)lowQ-=MOD;
            ll del=w*mm%MOD;
            sumWM-=del;
            if(sumWM<0)sumWM+=MOD;
        }
        // 2.左右端点位于不同块
        /*
            未被弹出的组满足 mx>x：
                贡献=x*Σ(w*mx)
        */
        ll C=xm*sumWM%MOD;

        /*
            被弹出的组满足 mx<=x：
                贡献=x(x+1)/2*Σw+1/2*Σ[w*mx(mx-1)]
        */
        C+=sum1(x)*lowW%MOD;
        C%=MOD;
        C+=lowQ*INV2%MOD;
        C%=MOD;
        ans+=C;
        ans%=MOD;
        // 3.更新单调栈，为后面的块做准备
        /*
            原来被弹出的起始块，其区间最大值全部变成 x
            当前块自己也能作为未来区间的起始块，
            当前块内有 x 种左端点选择。
            所以新组权值为lowW+x
        */
        ll newW=(lowW+xm)%MOD;
        stk.push_back({x,newW});
        sumWM+=newW*xm%MOD;
        sumWM%=MOD;
    }
    cout<<ans<<'\n';
}