塔子哥学算法

题解 E-字串-树状数组+差分做法

题解

未归档(82)

/ 注册

E-字串-树状数组+差分做法

666 浏览 4 回复 2020-09-12

塔子哥学算法

+关注

https://ac.nowcoder.com/acm/contest/7329/E

传送门：https://ac.nowcoder.com/acm/contest/7329/E

题目大意:给你一个长度为1e6的排列,让你统计区间[L,R]是一个值域为[L,R]的排列的区间个数.

昨天比赛的时候看了一下题目以为是析合树，就没写了emm，其实正解思路很简单。。

题目思路:

1.对于每一个点 x，我们求出以它为右端点的【合法左端点 L 的区间范围 $L_x$ 】使得 $\max _{i=L_x}^{x} a_{i}=x$
2.再求出以x为左端点的【合法右端点R的区间范围 $R_x$ 】使得 $\min _{i=x}^{R_x} a_{i}=x$
$例如：排列 3 \ 2 \ 1 \ 5 \ 4$
$第一个点3,它的L_1区间不存在,R_1区间为[3,5]$
$第二个点2,它的L_2区间为[2,2],R_2区间为[2,2]$
$第三个点1,它的L_3区间为[1,1],R_3区间不存在$
$第四个点5,它的L_4区间不存在,R_4区间为[5,5]$
$第五个点4,它的L_5区间为[1,4],R_5区间为不存在$

上述算法实现方式(可选): 单调栈 + 二分 / ST表 + 二分 (后者注意常数问题)

现在考虑两个点对 $i,j$ .当 $j\in R_i \land i\in L_j$ 时，点对产生贡献。

现在问题转化为：在序列上求合法的点对个数.

这里介绍一个较容易也是很经典的做法是：树状数组 + 扫描线 + 差分求贡献。

将所有的【合法右端点区间 $R_k$ 】拆成左右两个端点放入集合。然后对集合按端点大小升序排序。

之后遍历一遍数组,维护一个从左至右的指针 $i$ .对于i的情况进行简单讨论：

$1.当i进入到某个R_k的区间内(即i = R_k的左端点)。将树状数组中的位置k 加上 1.$

$2.当i出了某个R_k的区间(即i = R_k的右端点的下一个位置)。将树状数组中的位置k减去1$

$3.对于每个位置i.在树状数组中查询区间L_i的和即为i点对答案的贡献。$

$注意，有的点可能根本不存在合法的区间范围 L_i或者R_i，忽略他的贡献即可$

$时间复杂度:O(nlogn)$

AC代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44991792

树状数组二分扫描线思维

举报

收藏

赞 6

评论加载中...