莫队（mo）
题目描述
你有一个长度为 $n$ 的序列 $a_1\sim a_n$， 初始时 $a_i=i$。 有 $m$ 次操作， 第 $i$ 种操作是将 $[l_i,r_i]$ 这段区间赋值成 $a_{l_i}$。 现在有 $q$ 次询问， 每次询问依次执行 $[L,R]$ 这段区间内的操作之后序列中数的种类数， 询问之间独立。
输入格式
第一行两个正整数 $n,m$。
接下来 $m$ 行， 每行两个正整数 $l_i,r_i$， 表示操作区间。
接下来一行一个正整数 $q$。
接下来 $q$ 行， 每行两个正整数 $L_i,R_i$， 表示询问的区间。
输出格式
$q$ 行， 每行一个正整数表示答案。
样例 #1
样例输入 #1
3 5
1 3
2 3
1 2
2 3
2 2
4
1 3
2 3
1 2
4 5样例输出 #1
1
2
1
2提示
对于 $100\%$ 的数据， 满足 $1\le n,m,q\le 5\times10^5$， $1\le l_i\le r_i\le n$， $1\le L_i\le R_i\le m$。
| $n\le$ | $m\le$ | $q\le$ | 特殊性质 | 分值 | |
|---|---|---|---|---|---|
| $\operatorname{Subtask} 1$ | $10$ | $10$ | $10$ | $1$ | |
| $\operatorname{Subtask} 2$ | $100$ | $100$ | $100$ | $2$ | |
| $\operatorname{Subtask} 3$ | $3000$ | $3000$ | $3000$ | $15$ | |
| $\operatorname{Subtask} 4$ | $10^5$ | $10^5$ | $10^5$ | $A$ | $7$ |
| $\operatorname{Subtask} 5$ | $10^5$ | $10^5$ | $m$ | $B$ | $25$ |
| $\operatorname{Subtask} 6$ | $10^5$ | $10^5$ | $10^5$ | $20$ | |
| $\operatorname{Subtask} 7$ | $3\times 10^5$ | $3\times 10^5$ | $3\times 10^5$ | $15$ | |
| $\operatorname{Subtask} 8$ | $5\times 10^5$ | $5\times 10^5$ | $5\times 10^5$ | $15$ |
特殊性质 $A$： 保证 $L_i=1$。
特殊性质 $B$： 保证 $L_i=i$， $R_i=m-q+i$。