题解：P13662 「TPOI-5A」Luminescence

· · 题解

首先观察题目，很难不看出 a 对应的是前缀最小值，b 对应的是后缀最小值。

那么一个合法的 a 数组必然是单调不升的，且对于每个 a_i\lt a_{i-1} 的位置，一定有 q_i=a_i。而对于 a_i=a_{i-1} 的位置，则有 q_i\gt a_i 的限制。

同理，一个合法的 b 数组必然单调不降，且对于每个 b_i\lt b_{i+1} 的位置，一定有 q_i=b_i。而对于 b_i=b_{i+1} 的位置，则有 q_i\gt b_i 的限制。

另外，考虑数字 0 出现的位置 x，其会导致 i\lt x 时 a_i\gt 0,b_i=0 且 i\gt x 时 a_i=0,b_i\gt 0。所以有且仅有一个位置会满足 a_i=b_i=0。

到这里，我们完成了是否存在合法排列的判断。如果只是计算合法排列的数量，我们发现对于每个不确定 q_i 的位置 i，都会有形如 q_i\gt x_i 的限制。那么按照这个限制降序排序，根据当前可用的数字个数以及已经用掉的数字个数，很容易根据乘法原理计算出合法的方案数。

接下来考虑题目中给出的权值信息有什么用，可以看出其含义是计算所有区间的 \text{mex} 值并求和。

那么考虑枚举 \text{mex} 的值，变成对 i=1,2,\dots,n，去计算有多少区间满足 \text{mex}=i 并乘上贡献进行求和。再采用经典技巧，变成对每个 i，计算有多少区间满足 \text{mex}\ge i 并求和。即利用 x=\sum_{i=1}^{\infty} [x\ge i] 对式子进行拆分。

也就是：\sum_{1\le l\le r\le n}\text{MEX}(l,r)=\sum_{1\le l\le r\le n} \sum_{i=1}^{n} [\text{MEX}(l,r)\ge i]=\sum_{i=1}^{n} \sum_{1\le l\le r\le n} [\text{MEX}(l,r)\ge i]。

对于统计有多少区间满足 \text{mex}\ge i，则可以转化成有多少区间包含了 [0,i) 在内的所有数，进一步变成考虑 [0,i) 内数字出现的最左边位置 L 和最右边位置 R，那么对应方案数就是 L(N-R+1)（下标从 1 开始）。

到这里好像进行不下去了，我们考虑充分利用题目性质。注意到对于某个 x，若其没有出现在数组 a,b 中，这就意味着存在一个 \lt x 的数出现在了 x 的左边，且存在一个 \lt x 的数出现在了 x 的右边。分别考虑 a,b 中 \lt x 的最大数字出现的位置，以两个位置为左右端点的区间一定是包含 [0,x) 在内的所有数的最小区间。否则若存在 [0,x) 的一个数 y 不在这一区间内，那么这个数 y 一定会作为前缀最小值或者后缀最小值出现在 q 内，进一步会出现在 a,b 中不在区间内的某个位置，产生矛盾。

于是对于每个 i，我们可以计算出包含 [0,i) 内所有数的最小区间 [L,R]，从而计算出对应权值。同时我们会发现，对于给定的 a,b，一个合法排列的权值是确定的，于是我们只需计算出对应权值，以及合法排列的方案数就能计算出最终答案。

实现方面，在计算方案数时可以采用双指针来规避排序部分，同时也能完成权值的计算，时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define N 200020
#define MOD 998244353
int T,n,a[N],b[N];
int main()
{
    scanf("%d",&T);
    while(T--){
        int flg=1;
        scanf("%d",&n);
        a[0]=b[n+1]=n;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)scanf("%d",&b[i]);
        for(int i=1;i<=n;i++)if(a[i]>a[i-1])flg=0;
        for(int i=1;i<=n;i++)if(b[i]>b[i+1])flg=0;
        int l=1,r=n,m=-1;
        for(int i=1;i<=n;i++)if(b[i]==0)m=i;
        if(m==-1 || a[m]>0 || a[m-1]==0)flg=0;
        if(!flg){
            printf("0\n");
            continue;
        }
        int ans=0,tot=1,lst=n,cnt=0;
        while(l<=r){
            int x=max(a[l],b[r]),t=1ll*l*(n-r+1)%MOD;
            ans+=1ll*t*(lst-x)%MOD,ans%=MOD;
            cnt+=lst-x-1;
            lst=x;
            if(l==r)break;
            if(a[l]>b[r]){
                l++;
                while(a[l]==x && l<=n)l++,tot=1ll*tot*cnt%MOD,cnt--;
            }
            else{
                r--;
                while(b[r]==x && r>=1)r--,tot=1ll*tot*cnt%MOD,cnt--;
            }
        }
        printf("%lld\n",1ll*tot*ans%MOD);
    }
}