Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:1024 MB
统计

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

大样例