#NOIOLTG2022A. 丹钓战

丹钓战

题目描述

nn 个二元组 (ai, bi)(a_i,~b_i),编号为 11nn

有一个初始为空的栈 SS ,向其中加入元素 (ai, bi)(a_i,~b_i) 时,先不断弹出栈顶元素直至栈空或栈顶元素 (aj, bj)(a_j,~b_j) 满足 aiaja_i \ne a_jbibjb_i \le b_j,然后再将其加入栈中。

如果一个二元组入栈后栈内只有这一个元素,则称该二元组是“成功的”。

qq 个询问 [li, ri][l_i,~r_i] ,表示若将编号在 [li, ri][l_i,~r_i] 中的二元组按编号从小到大依次入栈,会有多少个二元组是“成功的”。

询问之间相互独立。

输入格式

第一行两个正整数 nnqq
第二行 nn 个正整数表示 aia_i
第三行 nn 个正整数表示 bib_i
接下来 qq 行,每行两个正整数 li, ril_i,~r_i, 表示一组询问。

输出格式

qq 行,每行一个自然数表示一组询问的答案。

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,~4] 为例。

一开始栈为 {}\{\}
加入 11 号二元组后栈为 {(3, 10)}\{(3,~10)\} ,栈中只有一个元素,该二元组是“成功的”。
加入 22 号二元组 (1, 10)(1,~10) 时,栈顶的 (3, 10)(3,~10)bb 值不大于 22 号二元组的,因此弹栈。此时栈空,22 号二元组入栈,栈为 {(1, 10)}\{(1,~10)\} ,该二元组是“成功的”。
加入 33 号二元组 (3, 2)(3,~2) ,此时栈顶元素与之 aa 值不同,bb 值比它更大,因而不需要弹栈,直接将 33 号二元组入栈,栈为 {(1, 10),(3, 2)}\{(1,~10), (3,~2)\} ,栈中有多个元素,该二元组不是“成功的”。
加入 44 号二元组 (1, 9)(1,~9) ,此时栈顶元素 (3, 2)(3,~2)bb 值比它小,弹栈。弹栈后栈顶元素 (1, 10)(1,~10)(1, 9)(1,~9)aa 值相同,继续弹栈。此时栈空,44 号二元组入栈,栈为 {(1, 9)}\{(1,~9)\},该二元组是“成功的”。

共有 33 个二元组是“成功的”,因而答案为 33

输入输出数据 2

stack2.instack2.ans

输入输出数据 3

stack3.instack3.ans

输入输出数据 4

stack4.instack4.ans

数据范围与提示

对于所有测试点:1n,q5×1051 \le n, q \le 5 \times 10^51ai,bin1 \le a_i, b_i \le n1lirin1 \le l_i \le r_i \le n

每个测试点的具体限制见下表:

测试点编号 特殊性质
131 \sim 3 n,q1000n,q \leq 1000
464 \sim 6 n5000n \leq 5000
7107 \sim 10 n,q105n,q \leq 10^5
111211 \sim 12 bi=ni+1b_i=n-i+1
131513 \sim 15 ai=ia_i=i
162016 \sim 20