问题描述
前两天,爱的战士ZZQ向我讨教了一个问题,这个问题可以用线性规划来描述。貌似用线性规划描述出来后,配合以单纯形法就可以求解了?
对于这种问题,我果断表示不会。后来ZZQ 告诉我,原来这个问题是可以转化为一个等价问题的:
一开始有$N(1 \leq N \leq 3*10^{5})$条线段,第i条线段覆盖的区间为$[L_i, R_i]$(其中$1 \leq L_i \leq R_i \leq 10^{6})$
然后有$M(1 \leq M \leq 3*10^{5})$个组,第i个组包含了$K_i(1 \leq K_i \leq 3*10^5)$个点,这$K_i$个点所在的位置分别用$P_1, P_2, ......, P_{k_i}$ 来表示,为了方便观察,我们令$1 \leq P_1 < P_2 < ...... < P_{k_i} \leq 10^{6}$
我们还可以知道,这M个组的点的数目加起来不超过$3*10^5$
现在的问题是,对于每一个组给出来的一系列的点,我们要求出一共有多少条线段,包含了给定的点中的至少一个点。
我对于这个转化的等价问题还是毫无头绪,于是决定私下找你来帮忙,为了不被爱的战士ZZQ 狂虐,你一定要帮帮我啊!
输入描述
多组数据(不超过30组)
对于每组数据,第一行两个整数$N$和$M$,分别代表线段的数量和$M$个分组。
接下来的$N$行,每行包含了2个整数$L_i$和$R_i$,表示第i条线段的起始和结束位置。
接下来的$M$行,每行第一个整数是$K$,表示该分组一共有$K$个点,接下来给出了$K$个点的坐标位置$P_1, P_2, ......, P_k(1 \leq P_1 < P_2 < ...... < P_k \leq 10^6)$
输出描述
对于每个分组,输出一个整数Ans,表示一共有Ans条线段,这Ans条线段分别包含了组里的至少一个点。
输入样例
3 3
1 3
4 5
6 7
3 1 4 7
2 4 5
1 8
输出样例
3
1
0