自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 23:16:28，当前版本为作者最后更新于2025-06-02 15:53:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我们把 $a$ 和 $b$ 按照从小到大的顺序排列，考虑刻画判定大小为 $m$ 的集合 $S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\}$ 合法的充要条件。为了满足条件，我们可以贪心，让 $S$ 中的元素与 $b_1 \sim b_m$ 配对，同时让不在 $S$ 中的元素与 $b_{m+1} \sim b_n$ 配对。

更具体地，集合 $S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\}$ 合法，当且仅当：

• 设在 $S$ 中的第 $i$ 小的元素为 $a_x$，则有 $a_x \gt b_i$；
• 设不在 $S$ 中的第 $i$ 小的元素为 $a_y$，则有 $a_y \lt b_{m+i}$。

于是，当 $m$ 确定时，我们可以设 $dp_{i,j}$ 表示考虑完 $a_1\sim a_i$ 且此时有 $j$ 个元素被选入 $S$ 中的方案数，枚举下一个元素是否选入 $S$ 即可得到转移方程为：

$$dp_{i,j}=dp_{i-1,j-1} \times [a_i \gt b_j]+dp_{i-1,j} \times [a_i \lt b_{m+j}] $$

$dp_{n,m}$ 即为 $l=m$ 且 $r=m$ 的询问的答案。我们对每一个 $0 \le m \le n$ 都求出 $dp_{n,m}$ 的值，再预处理一下前缀和即可做到 $\mathcal O(1)$ 回答单次询问。这样做的时间复杂度为 $\mathcal O(n^3+q)$，考虑优化。

我们需要对每一个 $m$ 都做一次 dp 是复杂度很大的原因之一，但是 $m$ 是判定条件中的一个参数，有没有什么办法把判定条件中的 $m$ 消掉呢？

我们可以做一个变形，把判定集合 $S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\}$ 合法的充要条件修改为：

• 设在 $S$ 中的第 $i$ 小的元素为 $a_x$，则有 $a_x \gt b_i$；
• 设不在 $S$ 中的第 $i$ 大的元素为 $a_y$，则有 $a_y \lt b_{n-i+1}$。

显然改之后的条件和改之前的条件是等价的，我们只是把不在 $S$ 中的元素的枚举顺序改变了，但这样做消去了判定条件中的 $m$。同时，看到这个 dp 形式，我们容易联想到分别对 $a$ 的前缀和后缀做一个 dp，最后把它们拼起来。

具体地，我们设 $f_{i,j}$ 表示在只受第一个条件的限制下考虑完 $a_1 \sim a_i$ 且此时有 $j$ 个元素被选入 $S$ 中的方案数，$g_{i,j}$ 表示在只受第二个条件的限制下考虑完 $a_n \sim a_i$ 且此时有 $j$ 个元素没有被选入 $S$ 中的方案数，枚举下一个元素的状态即可得到转移方程为：

$$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times[a_i \gt b_j]\\ g_{i,j}=g_{i+1,j-1}+g_{i+1,j}\times[a_i \lt b_{n-j+1}] $$

接下来我们考虑怎么把数组 $f$ 和数组 $g$ 拼起来。如果我们随便找一个位置 $w$ 将序列 $a$ 拆成 $a_1\sim a_w$ 的前缀与 $a_{w+1}\sim a_n$ 的后缀显然是有问题的——可能在 $a$ 的前缀中存在一个不在 $S$ 中的 $a_y$ 不满足 $a_y \lt b_{n-i+1}$ 的条件，也可能在 $a$ 的后缀中存在一个在 $S$ 中的 $a_x$ 不满足 $a_x \gt b_i$ 的条件。

于是，我们希望对每一个集合大小 $m$ 找到一个位置 $k$，使得 $a_1 \sim a_k$ 中的元素如果不在 $S$ 中则一定满足 $a_y \lt b_{n-i+1}$ 的条件，且 $a_{k+1} \sim a_m$ 中的元素如果在 $S$ 中则一定满足 $a_x \gt b_i$ 的条件。

因为现在集合大小 $m$ 是已知的，所以我们是希望判定集合 $S$ 合法的条件中出现 $m$ 的，于是我们可以再对判定集合 $S=\{a_{s_1},a_{s_2},\dots,a_{s_m}\}$ 合法的充要条件做一个变形：

• 设在 $S$ 中的第 $i$ 大的元素为 $a_x$，则有 $a_x \gt b_{m-i+1}$；
• 设不在 $S$ 中的第 $i$ 小的元素为 $a_y$，则有 $a_y \lt b_{m+i}$。

我们还是只改变了元素的枚举顺序，但这样的判定条件非常有利于我们找到满足要求的位置 $k$。现在，位置 $k$ 的要求变为了：

• 对于 $a_1 \sim a_k$ 中每一个不在 $S$ 中的元素 $a_y$，都满足 $a_y \lt b_{m+i}$；
• 对于 $a_{k+1} \sim a_n$ 中每一个在 $S$ 中的元素 $a_x$，都满足 $a_x \gt b_{m-i+1}$。

分析一下，如果我们有 $a_y \lt b_{m}$ 则我们一定有 $a_y \lt b_{m+i}$，而如果我们有 $a_x \gt b_m$ 则我们一定有 $a_x\gt b_{m-i+1}$，所以我们只需要满足 $a$ 的前缀都小于 $b_m$ 且 $a$ 的后缀都大于 $b_m$ 就可以满足条件了！于是我们所求的 $k$ 就是最大的满足 $a_k \lt b_m$ 的位置 $k$。

接下来我们只需要对于每一个 $m$ 找到划分位置 $k$，枚举前缀中在 $S$ 中的元素的个数 $c$，并将 $l=m$ 且 $r=m$ 的询问的答案加上 $f_{k,c} \times g_{k+1,n-k-m+c}$ 即可。

同样做一个前缀和即可做到 $\mathcal O(1)$ 回答单次询问，总时间复杂度 $\mathcal O(n^2+q)$，可以通过。

const int N=5e3+5,mod=998244353;
int n,a[N],b[N],f[N][N],g[N][N],q,sum[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
void solve(){
	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]=1,g[n+1][0]=1;
	for(int i=1;i<=n;i++){
		f[i][0]=f[i-1][0];
		for(int j=1;j<=i;j++){
			f[i][j]=f[i-1][j];
			if(a[i]>b[j]) add(f[i][j],f[i-1][j-1]);
		}
	}
	for(int i=n;i>=1;i--){
		g[i][0]=g[i+1][0];
		for(int j=1;j<=n-i+1;j++){
			g[i][j]=g[i+1][j];
			if(a[i]<b[n-j+1]) add(g[i][j],g[i+1][j-1]);
		}
	}
	for(int m=0;m<=n;m++){
		int k=0;
		while(k<n&&a[k+1]<b[m]) k++;
		for(int c=0;c<=m;c++) if(k>=c&&n-k-m+c>=0) add(sum[m],1ll*f[k][c]*g[k+1][n-k-m+c]%mod);
		if(m) add(sum[m],sum[m-1]);
	}
	cin>>q;
	for(int i=1,l,r;i<=q;i++){
		cin>>l>>r;
		if(l==0) cout<<sum[r]<<endl;
		else cout<<(sum[r]-sum[l-1]+mod)%mod<<endl;
	}
}