莫队(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$。