P16327 线段

你有一个可重集 $S$，每个元素是一个线段。初始你有 $n$ 个元素，第 $i$ 个元素为线段 $[l_i,r_i]$。 接下来有 $q$ 次操作，每次操作给出一个线段 $[L,R]$。**同时**检查当前的每个元素 $[l_i,r_i]$。若其与线段 $[L,R]$ 有交，则将相交的部分从原线段中分割出来，然后将剩下的几部分作为新的元素加入，并把原来的元素删掉。**新的元素不会参与本次操作，线段 $[L,R]$ 不会被加入 $S$**。 形式化地，令 $l'=\max(l_i,L) $，$r'=\min(r_i,R)$，若 $l'\le r'$： - 将线段 $[l', r']$ 加入 $S$。 - 若 $l_i

第一行两个正整数 $n,q$，表示初始元素个数和操作次数。 接下来 $n$ 行，每行两个正整数 $l_i,r_i$，表示每个初始元素 $[l_i,r_i]$。 接下来 $q$ 行，每行两个正整数 $L_i,R_i$，表示每次操作给出的区间 $[L_i,R_i]$。

输出 $q$ 行，每行一个整数表示每次操作后的元素个数。

**【样例解释 1】** 初始有 $5$ 个线段 $[1,1],[10,10],[3,3],[3,3],[1,10]$。 第一个操作给定线段 $[2,8]$，与其有交的线段有 $[3,3],[3,3],[1,10]$，操作后 $[3,3]$ 保持不变，$[1,10]$ 变为 $[1,1],[2,8],[9,10]$，共有 $7$ 个元素。 第二个操作给定线段 $[3,10]$，与其有交有 $[10,10],[3,3],[3,3],[2,8],[9,10]$，其中只有 $[2,8]$ 会变为 $[2,2],[3,8]$，共有 $8$ 个元素。 第三个操作给定线段 $[1,3]$，与其相交的会变化的元素只有 $[3,8]$ 会变为 $[3,3],[4,8]$，共有 $9$ 个元素。 **【数据范围】** **本题使用子任务捆绑**。 对于所有测试数据，$1 \le n,q \le 5\times10^5$，$1\le l_i \le r_i \le 10^9$，$1 \le L_i \le R_i \le 10^9$。 |子任务编号|$n,q\le$|特殊性质|分值| |:-:|:-:|:-:|:-:| |$1$|$200$|无|$20$| |$2$|$2000$|无|$20$| |$3$|$5\times 10^5$|有|$20$| |$4$|$5\times 10^5$|无|$40$| - 特殊性质：保证 $L_i = 1$。