題面：

（這個(gè)沒(méi)交洛谷，給學(xué)弟寫的。）

\(O(n^3)\)

考慮直接求出所有 \(ans_i\)，前綴和回答詢問(wèn)。
\(a,b\) 先排序。由于我們只關(guān)心英雄的集合，所以怪獸我們貪心選擇，如果我們選這個(gè)英雄那么選最前面的怪獸，否則選后面第一個(gè)能打死自己的怪獸。顯然，合法方案怪獸的前綴會(huì)被英雄打死，后綴會(huì)打死英雄，顯然了就不證。
\(f_{i,j}\)：前 i 個(gè)英雄匹配了 j 個(gè)怪獸的方案數(shù)。
這時(shí)我們發(fā)現(xiàn)我們選后面第一個(gè)能打死自己的怪獸可能會(huì)礙后面想打怪獸的英雄的事，所以枚舉斷點(diǎn) \(k\)。
我們讓欽定去悲傷的英雄去選擇 \([k+1,n]\) 的怪獸，高興的英雄去選 \([1,k]\) 的怪獸。

\(f_{i,j}=f_{i-1,j-1}[b_j<a_i]+f_{i-1,j}[b_{k+1+(i-1-j)}>a_i]\)

\(O(n^2)\)

我們找到 \(a_p<b_k<a_{p+1}\) 這樣的 \(p\)。
那么 \([1,p]\) 的英雄肯定能找到比自己大的怪獸，\([p+1,n]\) 的英雄肯定能找到比自己小的怪獸，顯然內(nèi)部不沖突。
那么我們只需要考慮前綴是否能找到比自己小的怪獸，后綴能否找到比自己大的怪獸。

\(f_{i,j}\)：\([1,i]\) 的英雄 \(j\) 個(gè)找到了比自己小的怪獸的方案數(shù)。
\(g_{i,j}\)：\([i,n]\) 的英雄 \(j\) 個(gè)找到了比自己大的怪獸的方案數(shù)。

下面是轉(zhuǎn)移（\(g\) 我們倒著更新，那么肯定是取后綴怪獸）：

\(f_{i,j}=f_{i-1,j-1}[b_j<a_i]+f_{i-1,j}\)
\(g_{i,j}=g_{i+1,j-1}[b_{n-(j-1)}>a_i]+g_{i+1,j}\)

那么我們枚舉一個(gè)數(shù) \(c\)，表示 \([1,p]\) 有 \(c\) 個(gè)高興的英雄，那么 \([p+1,n]\) 有 \((k-c)\) 個(gè)高興的英雄。
直接合并就好了。

\(ans_m=\sum_{c=0}^m f_{p,c}×g_{p+1,n-p-(k-c)}\)