由于二分图匹配是拟阵，所以可以按照 $p_i$ 从大到小的顺序依次考虑，只要有解就加入。

需要快速判断是否存在完美匹配。由 Hall 定理，存在完美匹配等价于对任意的 $S\subseteq X$ 都有 $|N(S)|\ge |S|$。由于 $l_i\le l_{i+1},r_i\le r_{i+1}$，因此只需检查所有区间。即对任意 $0\le x\le y\le n-1$ 都有 $\sum_{i=l_x}^{r_y-1}a_i\ge y-x+1$，即 $sum(r_y)-sum(l_x)\ge y-x+1$。用线段树维护是否存在不合法情况即可。

时间复杂度 $O(t+n\log n)$。