3653. [NOI Online 2022 1st]丹钓战

【题目描述】

有$n$个二元组$(a_i,b_i)$，编号为$1$到$n$。

有一个初始为空的栈 $S$，向其中加入元素$(a_i,b_i)$时，先不断弹出栈顶元素直至栈空或栈顶元素$(a_j,b_j)$满足$a_i\neq a_j$且 $b_i< b_j$，然后再将其加入栈中。

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

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

询问之间相互独立。

【输入格式】

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数表示 $a_i$。

第三行 $n$ 个正整数表示 $b_i$。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$, 表示一组询问。

【输出格式】

$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。

【数据规模与约定】

对于所有测试点：$1\leq n,q\leq 5\times 10^5,1\leq a_i,b_i\leq n,1\leq l_i,r_i\leq n$。

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

【来源】

NOI Online 2022 1st 提高组 T1