题目描述
【题目描述】
有 n 个二元组 (ai , bi)，编号为 1 到 n。
有一个初始为空的栈 S，向其中加入元素 (ai , bi) 时，先不断弹出栈顶元素直至栈空或栈顶元素 (aj , bj ) 满足 ai ≠ aj 且 bi < bj，然后再将其加入栈中。
如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。
有 q 个询问 [li , ri]，表示若将编号在 [li , ri] 中的二元组按编号从小到大依次入栈，会有多少个二元组是“成功的”。
询问之间相互独立。
输入
【输入格式】
从文件 stack.in 中读入数据。
第一行两个正整数 n, q。
第二行 n 个正整数表示 ai。
第三行 n 个正整数表示 bi。
接下来 q 行，每行两个正整数 li , ri, 表示一组询问。
输出
【输出格式】
输出到文件 stack.out 中。 【输入格式】
从文件 stack.in 中读入数据。
第一行两个正整数 n, q。
第二行 n 个正整数表示 ai。
第三行 n 个正整数表示 bi。
接下来 q 行，每行两个正整数 li , ri, 表示一组询问。
q 行，每行一个自然数表示一组询问的答案。
样例输入 复制
10 4
3 1 3 1 2 3 3 2 1 1
10 10 2 9 7 5 4 7 6 1
1 4
7 8
7 10
1 8
样例输出 复制
3
2
2
3
提示
【样例解释】
以第一次询问 [1, 4] 为例。
- 一开始栈为 {}。
- 加入 1 号二元组后栈为 {(3, 10)}，栈中只有一个元素，该二元组是“成功的”。
- 加入 2 号二元组 (1, 10) 时，栈顶的 (3, 10) 的 b 值不大于 2 号二元组的，因此弹栈。此时栈空，2 号二元组入栈，栈为 {(1, 10)}，该二元组是“成功的”。
- 加入 3 号二元组 (3, 2)，此时栈顶元素与之 a 值不同，b 值比它更大，因而不需要弹栈，直接将 3 号二元组入栈，栈为 {(1, 10),(3, 2)}，栈中有多个元素，该二元组不是“成功的”。
- 加入 4 号二元组 (1, 9)，此时栈顶元素 (3, 2) 的 b 值比它小，弹栈。弹栈后栈顶元素 (1, 10) 与 (1, 9) 的 a 值相同，继续弹栈。此时栈空，4 号二元组入栈，栈为 {(1, 9)}，该二元组是“成功的”。
- 共有 3 个二元组是“成功的”，因而答案为 3。
【样例 2,3,4】
见选手目录下的 stack/stack*.in 与 stack/stack*.ans 。
【数据范围与提示】
对于所有测试点：1 ≤ n, q ≤ 5 × 105，1 ≤ ai , bi ≤ n，1 ≤ li ≤ ri ≤ n。
每个测试点的具体限制见下表：
|
测试点编号
|
特殊限制
|
|
1 ∼ 3
|
n, q ≤ 1000
|
|
4 ∼ 6
|
n ≤ 5000
|
|
7 ∼ 10
|
n, q ≤ 105
|
|
11 ∼ 12
|
bi = n − i + 1
|
|
13 ∼ 15
|
ai = i
|
|
16 ∼ 20
|
无
|