P5401: 丹钓战（stack）

---

【题目描述】

【题目描述】
有 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 行，每行一个自然数表示一组询问的答案。

【提示】

【样例解释】

以第一次询问 [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 × 10⁵，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	无

 

题目类型~

NOIOnline2022提高级 

咻咻~

提交答案 状态 返回