本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-09 08:16:38

题意

给定两个长为 $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;
}