专栏文章

[题解] CF2045E Narrower Passageway

MMonke_FClBrI
CF2045E题解参与者 3已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miqo9sgk
此快照首次捕获于
2025/12/04 08:03
3 个月前
此快照最后确认于
2025/12/04 08:03
3 个月前
查看原文
一个简单一点的做法。
首先容易发现求的就是所有方案的总权值除以方案数 2n2^n。
我们发现一个区间权值的计算方式是：若两行分别的最大值相等则为 00，否则为较小者。这个东西看上去就比较抽象，应该需要一些巧妙的转化。
设两行分别为序列 a,ba,b，某区间在两行的最大值分别为 m1,m2m_1,m_2，考虑把该区间权值转化为：
m1+m2−[m1=max⁡(m1,m2)]⋅m1−[m2=max⁡(m1,m2)]⋅m2m_1+m_2-[m_1=\max(m_1,m_2)]\cdot m_1-[m_2=\max(m_1,m_2)]\cdot m_2
考虑统计每个数对答案的贡献。
先思考 m1m_1 的贡献怎么算。对于第一行的每个元素，可以用单调栈求出极大的包含 ii 位置的区间 [Li,Ri][L_i,R_i]，使得：
  • ∀j∈[Li,i),aj≤ai\forall j\in[L_i,i),a_j\le a_i
  • ∀j∈(i,Ri],aj<ai\forall j\in(i,R_i],a_j<a_i
上下符号不同是为了防止算重。然后它的贡献就是 aia_i 乘以 存在一个区间的左端点在 [Li,i][L_i,i]、右端点在 [i,Ri][i,R_i] 的方案数。
考虑这个方案数如何计算。要想构成一个极长的无雾区间 [l,r][l,r]，“是否有雾的状态”确定的位置是 [l−1,r+1][l-1,r+1]（l−1,r+1l-1,r+1 必须有雾，[l,r][l,r] 必须没有，忽略 l=1l=1 或 r=nr=n 的情况），不确定的位置有 2l−2⋅2n−r−12^{l-2}\cdot 2^{n-r-1} 种方案。那么总共的状态数就是
∑l=Lii∑r=iRi2l−2⋅2n−r−1=(∑l=Lii2l−2)(∑r=iRi2n−r−1)=(2i−1−2Li−2)(2n−i−2n−Ri−1)\sum\limits_{l=L_i}^i\sum\limits_{r=i}^{R_i}2^{l-2}\cdot 2^{n-r-1}=(\sum\limits_{l=L_i}^i 2^{l-2})(\sum\limits_{r=i}^{R_i}2^{n-r-1})=(2^{i-1}-2^{L_i-2})(2^{n-i}-2^{n-R_i-1})
这样就容易计算了。至于 l=1l=1 或 r=nr=n，只要假装 2−1=02^{-1}=0 就可以了。
于是 m1m_1 的贡献就算完了，m2m_2 同理。
考虑式子的后面两项，我们也可以用单调栈求出极长的区间 [Li,Ri][L_i,R_i]，使得：
  • ∀j∈[Li,i),aj≤ai\forall j\in[L_i,i),a_j\le a_i
  • ∀j∈(i,Ri],aj<ai\forall j\in(i,R_i],a_j<a_i
  • ∀j∈[Li,Ri],bj≤ai\forall j\in[L_i,R_i],b_j\le a_i
然后和上面一样计算即可。
代码还是比较好写的。注意一些细节的处理，具体见代码。
预处理二的幂次即可做到 O(n)O(n)。

代码

CPP
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define SZ(x) (int)(x).size()
using namespace std;
const int N=1e5+5,mod=998244353,i2=(mod+1)/2;
int n,a[N],b[N],st[N],t,L[N],R[N],mi[N],ans;
inline int Mi(int x){return x<0?0:mi[x];}
inline int cal(int l,int m,int r){
	if(l>m||m>r)return 0;
	return (Mi(m-1)+mod-Mi(l-2))*(Mi(n-m)+mod-Mi(n-r-1))%mod;
}
inline void wrk1(){
	for(int i=n;i;i--){
		while(t&&a[i]>a[st[t]])L[st[t--]]=i+1;
		st[++t]=i;
	}
	while(t)L[st[t--]]=1;
	// 注意上下弹栈符号区别。
	for(int i=1;i<=n;i++){
		while(t&&a[i]>=a[st[t]])R[st[t--]]=i-1;
		st[++t]=i;
	}
	while(t)R[st[t--]]=n;
	for(int i=1;i<=n;i++)ans=(ans+cal(L[i],i,R[i])*a[i])%mod;
}
inline void wrk2(){
	for(int i=n;i;i--){
		while(t&&(b[i]>a[st[t]]||a[i]>a[st[t]]))L[st[t--]]=i+1;
		if(a[i]>=b[i])st[++t]=i;else L[i]=i+1;
	}
	while(t)L[st[t--]]=1;
	// 注意上下弹栈符号区别。
	for(int i=1;i<=n;i++){
		while(t&&(b[i]>a[st[t]]||a[i]>=a[st[t]]))R[st[t--]]=i-1;
		if(a[i]>=b[i])st[++t]=i;else R[i]=i-1;
	}
	while(t)R[st[t--]]=n;
	for(int i=1;i<=n;i++)ans=(ans+mod-cal(L[i],i,R[i])*a[i]%mod)%mod;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	mi[0]=1;for(int i=1;i<=n;i++)mi[i]=(mi[i-1]*2)%mod;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	wrk1(),wrk2();
	swap(a,b);
	wrk1(),wrk2();
	for(int i=1;i<=n;i++)ans=ans*i2%mod;
	cout<<ans<<'\n';
	return 0;
}
（逃

评论

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

正在加载评论...