P12558 [UOI 2024] Heroes and Monsters 题解

· · 题解

我们把 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}\} 合法，当且仅当：

于是，当 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}] 我们需要对每一个 $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)$，可以通过。 ```c++ 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; } } ```