专栏文章

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

lluuia
P14224题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minlyje5
此快照首次捕获于
2025/12/02 04:34
3 个月前
此快照最后确认于
2025/12/02 04:34
3 个月前
查看原文

Question

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

Solution

首先不难想到分治，我们按照区间 [l,r][l,r] 当中的最大值将当前 [l,r][l,r] 划分为若干个子段。
不妨设这几段的长度分别为 a1,a2,⋯ ,ama_1,a_2,\cdots,a_m，那么对于 kk 的贡献应该为：
∑i=1m−k(ai+1)×(ai+k+1)\sum_{i=1}^{m-k} (a_i + 1)\times(a_{i+k} + 1)
那么只需要把 aa 数组反转然后直接 NTT 卷积即可。继续分治按照上面分出的子段递归下去即可，时间复杂度 O(nlog⁡n)O(n \log n)。

Code

省略了多项式模板。
CPP
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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...