题解：P13662 「TPOI-5A」Luminescence

· · 题解

题外话

赛时还在感叹这题怎么可能只有黄。

思路

考虑我们从前缀最小值和后缀最小值中能得到什么信息。显然如果一个位置最小值发生变化，那么这个位置的值就能确定。那么我们就可以得到一些已经确定位置的数和一些没有确定位置的数（这不废话吗）。

我们从小到大枚举 \operatorname{mex} 函数可能的值 x，设 0 到 x-1 中所有已经确定位置的数的位置的最左端和最右端为 l,r。

我们惊喜的发现：若 x 为还未确定位置的数，那它的位置必须在 l 到 r 之间（因为 l 到 r 是所有小于 x 且位置确定的数，若 x 不在 l 到 r 之间，那它一定在 a 或 b 数组中出现，那样位置就确定了），而这样的话 \operatorname{mex} 函数的值就一定不为 x，因为若把 0 到 x-1 中的所有数都包含了那也一定包含了 x，此时贡献为 0；若 x 为确定位置的数，设其位置为 y，那么 \operatorname{mex} 函数值为 x 的区间就必须包含 (l,r) 且不覆盖 y，这个贡献可以直接算。

分析完之后，我们发现对于所有可能的魔怔排列，这些贡献都是一样的，将以上的结果乘上魔怔排列方案数即可。这个怎么算呢？若 x 为确定位置的数，那它的位置已经确定了（又说废话）；若 x 为还未确定位置的数，那它可以在 (l,r) 中任意一个不是已经有数的位置。由于已经填了 x 个数，所以有 r-l+1-x 个位置可以填，累计相乘即可。

时间复杂度 O(n)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int t,n,a[200005],b[200005],c[200005],d[200005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        for(int i=1;i<=n;i++){
            if(i==1||a[i]!=a[i-1])c[i]=a[i],d[a[i]]=i;
        }
        for(int i=n;i>=1;i--){
            if(i==n||b[i]!=b[i+1])c[i]=b[i],d[b[i]]=i;
        }
        int l=d[0],r=d[0],ans=n,tmp=1;
        for(int i=1;i<=n-1;i++){
            if(d[i]){
                if(d[i]<l)ans+=i*(l-d[i])%mod*(n-r+1)%mod,ans%=mod,l=d[i];
                else ans+=i*(d[i]-r)%mod*l%mod,ans%=mod,r=d[i];
            }
            else{
                tmp*=r-l+1-i,tmp%=mod;
            }
        }
        cout<<ans*tmp%mod<<"\n";
        for(int i=1;i<=n;i++)c[i]=d[i]=0;
    }
    return 0;
}