题解：P14224 [ICPC 2024 Kunming I] 子数组

· · 题解

Question

给定序列 a，对于 k \in [1,n] 求出有多少个子数组满足区间最大值出现了 k 次。

Solution

首先不难想到分治，我们按照区间 [l,r] 当中的最大值将当前 [l,r] 划分为若干个子段。

不妨设这几段的长度分别为 a_1,a_2,\cdots,a_m，那么对于 k 的贡献应该为：

\sum_{i=1}^{m-k} (a_i + 1)\times(a_{i+k} + 1)

那么只需要把 a 数组反转然后直接 NTT 卷积即可。继续分治按照上面分出的子段递归下去即可，时间复杂度 O(n \log n)。

Code

省略了多项式模板。

const int N = 1e6 + 30,mod = 998244353;int as[N],mx[N][25];vector<ll> H[N];
ll qry(ll l,ll r){ll k = log2(r - l + 1);return max(mx[l][k],mx[r - (1 << k) + 1][k]);}
void solve(ll l,ll r){if(l > r) return;if(l == r){as[1]++;return;}vector<ll> ve;
    ll v = qry(l,r);auto it = lower_bound(H[v].begin(),H[v].end(),l);ve.pb(l - 1);while(it != H[v].end() && *it <= r) ve.pb(*it),it++;
    ll m = ve.size();ve.pb(r + 1);Polynomial F(m),G(m);
    For(i,1,m) F[i - 1] = ve[i] - ve[i - 1],G[m - i] = F[i - 1];auto Q = F * G;
    For(i,0,m - 2) as[m - i - 1] = (as[m - i - 1] + Q[i]) % mod;For(i,1,m) solve(ve[i - 1] + 1,ve[i] - 1);
}void sol(){ll n;fsti  >> n;vector<ll> a(n);for(auto &x : a) fsti  >> x;
    auto b = a;sort(b.begin(),b.end()),b.erase(unique(b.begin(),b.end()),b.end());
    for(auto &x : a) x = lower_bound(b.begin(),b.end(),x) - b.begin();
    For(i,0,n - 1) H[a[i]].pb(i);For(i,0,n - 1) mx[i][0] = a[i];
    For(j,1,19) For(i,0,n - (1 << j)) mx[i][j] = max(mx[i][j - 1],mx[i + (1 << j - 1)][j - 1]);
    solve(0,n - 1);ll o = 0;For(i,1,n) o = (o + 1ll * as[i] * as[i] % mod * i) % mod;fsto  << o << '\n';
    For(i,0,n * 2 + 100) as[i] = 0,H[i].clear();
}int main(){
    // freopen("input.in","r",stdin);
    ll T;fsti >> T;while(T--) sol();return 0;
}