当前位置:首页 > 数据结构 > 树状数组 > 正文
洛谷P8252丹钓战[NOI Online 2022]
361+

题目大意:n个二元组 $(a_i, b_i)$,编号为1到n,m次询问,每次询问区间[x, y]的二元组依次入单调栈,维护栈中元素相邻的a不相等且b递增,问其中有多少个二元组能放到栈底?

题目描述

有 $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$ 行,每行一个自然数表示一组询问的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

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】**

见附件 $\texttt{stack/stack*.in}$ 与 $\texttt{stack/stack*.ans}$。

链接:<https://pan.baidu.com/s/14XxLN63bxvpJAod81foGOg>
提取码:gugu

**【数据范围与提示】**

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

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

| 测试点编号 | 特殊性质 |
| ———— | ————— |
| $1 \sim 3$ | $n,q \leq 1000$ |
| $4 \sim 6$ | $n \leq 5000$ |
| $7 \sim 10$ | $n,q \leq 10^5$ |
| $11 \sim 12$ | $b_i=n-i+1$ |
| $13 \sim 15$ | $a_i=i$ |
| $16 \sim 20$ | 无 |

解题思路

区间[x, y]中的二元组,能到达栈底,就能弹栈至x-1的位置,甚至更多。

也就是说,我们只需要预处理出每个二元组入栈后的前一个是谁,如果他在x的左边,就可以实现他是栈底。

预处理p[i]表示二元组i能弹栈到达的位置j,问题就转换成求区间[x, y]中有多少个数字小于x。(感谢shenghang16提供思路)

可以使用离线树状数组或者主席树解决。

程序实现

按照左端点排序,依次处理出每个左端点x时刻前,小于左端点的值有多少个(减);显然,全部都是小于左端点,有x-1个!

按照右端点排序,依次处理出每个右端点y时刻后,小于左端点的值有多少个(加);这里可以用树状数组维护。

利用前缀和,右端点时刻-左端点时刻即答案。

注意,树状数组难以处理位置0,我们可以讲位置全部加1。

跟时间有关,可以用可持久化线段树——主席树解决。

报歉!评论已关闭.