P4477 [BJWC2018] 基础匹配算法练习题

小 S 最近学会了二分图匈牙利匹配算法。 现在二分图的 X 部有 $N$ 个数字 $A_i$，Y 部有 $K$ 个数字 $C_i$。 已知如果 $A_i + C_j \le Z$，那么 $A_i$ 和 $C_j$ 之间就有一条边，求二分图（X，E，Y）的最大匹配数。 小 S 是初学者，所以她想做多做一些练习来巩固知识。于是她找到了一个长度为 $M$ 的正整数数组 $B$，每次她会在 $B$ 数组中抽取一段连续的区间 $[L_i,R_i]$，把区间 $[L_i,R_i]$ 的所有数字作为二分图 Y 部的 $K$ 个数字 $C_i$，然后重新求一次二分图最大匹配数。 小 S 打算一共做 $Q$ 次练习，但是她不知道每次计算出的答案对不对，你能帮帮她吗？

无

无

测试数据编号|$N$|$M$|$Q$ :-:|:-:|:-:|:-: $1 \sim 4$|$\le 50$|$\le 50$|$\le 50$ $5 \sim 10$|$\le 2501$|$\le 2501$|$\le 2501$ $11\sim 14$|$\le 152501$|$\le 45678$|$\le 45678$ $15 ,16$|$\le 152501$|$\le 50$|$\le 52501$ $17 \sim 20$|$\le 152501$|$\le 52501$|$\le 52501$ 对于 $100\%$ 的数据，$1 \le A_i,B_i,Z \le 10^9$，$1 \le L_i \le R_i \le Q$。 保证数据有一定梯度。