[题解] CF2045E Narrower Passageway

· · 题解

一个简单一点的做法。

首先容易发现求的就是所有方案的总权值除以方案数 2^n。

我们发现一个区间权值的计算方式是：若两行分别的最大值相等则为 0，否则为较小者。这个东西看上去就比较抽象，应该需要一些巧妙的转化。

设两行分别为序列 a,b，某区间在两行的最大值分别为 m_1,m_2，考虑把该区间权值转化为：

m_1+m_2-[m_1=\max(m_1,m_2)]\cdot m_1-[m_2=\max(m_1,m_2)]\cdot m_2

考虑统计每个数对答案的贡献。

先思考 m_1 的贡献怎么算。对于第一行的每个元素，可以用单调栈求出极大的包含 i 位置的区间 [L_i,R_i]，使得：

上下符号不同是为了防止算重。然后它的贡献就是 a_i 乘以 存在一个区间的左端点在 [L_i,i]、右端点在 [i,R_i] 的方案数。

考虑这个方案数如何计算。要想构成一个极长的无雾区间 [l,r]，“是否有雾的状态”确定的位置是 [l-1,r+1]（l-1,r+1 必须有雾，[l,r] 必须没有，忽略 l=1 或 r=n 的情况），不确定的位置有 2^{l-2}\cdot 2^{n-r-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=1 或 r=n，只要假装 2^{-1}=0 就可以了。

于是 m_1 的贡献就算完了，m_2 同理。

考虑式子的后面两项，我们也可以用单调栈求出极长的区间 [L_i,R_i]，使得：

然后和上面一样计算即可。

代码还是比较好写的。注意一些细节的处理，具体见代码。

预处理二的幂次即可做到 O(n)。

代码

#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;
}

（逃