P16327 Segments

You have a multiset $S$, where each element is a segment. Initially, there are $n$ elements, and the $i$-th element is the segment $[l_i,r_i]$. Then there are $q$ operations. In each operation, a segment $[L,R]$ is given. We **simultaneously** check every current element $[l_i,r_i]$. If it intersects with $[L,R]$, then the intersecting part is split out from the original segment, and the remaining parts are added back as new elements, while the original element is removed. **The newly added elements do not participate in the current operation, and the segment $[L,R]$ itself is not added into $S$.** Formally, let $l'=\max(l_i,L)$ and $r'=\min(r_i,R)$. If $l'\le r'$, then: - Add the segment $[l',r']$ to $S$. - If $l_i

The first line contains two positive integers $n,q$, denoting the initial number of elements and the number of operations. The next $n$ lines each contain two positive integers $l_i,r_i$, describing the initial segments $[l_i,r_i]$. The next $q$ lines each contain two positive integers $L_i,R_i$, describing the segment $[L_i,R_i]$ given in each operation.

Print $q$ lines, each containing a single integer — the number of elements after the corresponding operation.

**Explanation for Sample 1** Initially there are $5$ segments: $[1,1],[10,10],[3,3],[3,3],[1,10]$. For the first operation, the given segment is $[2,8]$. The segments intersecting it are $[3,3],[3,3],[1,10]$. After the operation, both $[3,3]$ remain unchanged, while $[1,10]$ becomes $[1,1],[2,8],[9,10]$. So there are $7$ elements in total. For the second operation, the given segment is $[3,10]$. The intersecting elements are $[10,10],[3,3],[3,3],[2,8],[9,10]$. Among them, only $[2,8]$ changes, becoming $[2,2],[3,8]$. So there are $8$ elements in total. For the third operation, the given segment is $[1,3]$. The only intersecting element that changes is $[3,8]$, which becomes $[3,3],[4,8]$. So there are $9$ elements in total. **Constraints** For all test cases, $1 \le n,q \le 5\times 10^5$, $1\le l_i \le r_i \le 10^9$, and $1 \le L_i \le R_i \le 10^9$. | Subtask | $n,q\le$ | Special Property | Score | | :-----: | :------------: | :--------------: | :---: | | $1$ | $200$ | None | $20$ | | $2$ | $2000$ | None | $20$ | | $3$ | $5\times 10^5$ | Yes | $20$ | | $4$ | $5\times 10^5$ | None | $40$ | - Special property: It is guaranteed that $L_i=1$.