P12558 题解

· · 题解

题意

给定两个长为 n 的数组 a,b，元素两两不同。q 次询问，每次给出 l,r，求有多少大小在 [l,r] 内的集合 S 满足存在排列 p，使得 a_i>b_{p_i} 的 i 组成的集合恰为 S。q-1\le n\le 5000。

题解

首先枚举 \left|S\right|=x，考虑如何判断一个集合 S 是否合法。此时令 S 内元素与前 x 小的元素匹配，S 外元素与剩余元素匹配，且两部分均将 a,b 分别从小到大排序后对应位置匹配一定不劣。因此先将 a,b 排序，这样就可以设 f_{i,j} 表示前 i 个数中选进 S 了 j 个，且前 i 个匹配均合法的方案数。转移时枚举第 i 个数的情况，只进行合法转移即可。时间复杂度 O(n^3)。

考虑优化这个过程，注意到 f_{i,j} 转移时若令其在 S 内，则要 a_i>b_j，否则要 a_i<b_{x+i-j}。这里前者与 x 无关，而后者有关，复杂度瓶颈也在这里。若把顺序倒过来，即 g_{i,j} 表示 [i,n] 中有 j 个在 S 外的合法方案数，则令其在 S 外只需 a_{i}<b_{n-j+1}，否则需要 a_{i}>b_{x-n+i+j}，反而使得在 S 外的判断不再依赖 x 的值了。若能把不依赖 x 值的两部分拼成答案，就可以降低复杂度。

考虑找到一个位置 p，使得其为 a 中最后一个满足 a_p<b_x 的位置，此时可以确定 [1,p] 内的 a_i 放到 S 外一定合法，[p+1,n] 内的 a_i 放到 S 内也一定合法，此时只需要保证前面放到 S 内和后面放到 S 外的匹配合法即可，这正是 f,g 的转移中不依赖 x 的那部分。因此只考虑这些限制转移出 f,g 数组，对每个 x 找到对应的 p，\left|S\right|=x 的答案即为 \sum_{j=0}^x f_{p,j}\times g_{p+1,n-i-p+j}。对答案求前缀和即可回答 [l,r] 的区间询问，时间复杂度为 O(n^2+q)。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e3+10;
const int mod=998244353;
void add(int &a,int b) {a+=b;if(a>=mod)a-=mod;}
int n,q,a[N],b[N],r[N],f[N][N],g[N][N];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(a+1,a+1+n),sort(b+1,b+1+n),f[0][0]=g[n+1][0]=1;
    for(int i=1;i<=n;i++) for(int j=0;j<=i;j++)
    {
        f[i][j]=f[i-1][j];
        if(j&&a[i]>b[j]) add(f[i][j],f[i-1][j-1]);
    }
    for(int i=n;i>=1;i--) for(int j=0;j<=n-i+1;j++)
    {
        g[i][j]=g[i+1][j];
        if(j&&a[i]<b[n-j+1]) add(g[i][j],g[i+1][j-1]);
    }
    int p=0;
    for(int i=0;i<=n;i++)
    {
        while(p<n&&a[p+1]<b[i]) p++;
        for(int j=0;j<=i;j++) add(r[i],1ll*f[p][j]*g[p+1][n-i-p+j]%mod);
    }
    for(int i=1;i<=n;i++) add(r[i],r[i-1]);
    cin>>q;
    while(q--)
    {
        int x,y; cin>>x>>y;
        cout<<(r[y]+mod-(x?r[x-1]:0))%mod<<'\n';
    }
    return 0;
}