loj 6062 「2017 山东一轮集训 Day2」Pair 题解

Description

题目链接

给出一个长度为 $n$ 的数列 $\{a_i\}$ 和一个长度为 $m$ 的数列 $\{b_i\}$,求 $\{a_i\}$ 有多少个长度为 $m$ 的连续子数列能与 $\{b_i\}$ 匹配。

两个数列可以匹配,当且仅当存在一种方案,使两个数列中的数可以两两配对,两个数可以配对当且仅当它们的和不小于 $h$。

对于$100\%$的数据,$1\leq m\leq n \leq 150000$。

Solution

很明显,我们可以把检验配对的不等式变形:

$$a_i + b_i \ge h$$

$$a_i \ge h- b_i$$

令$b_i’=h-b_i$

要使其可完全匹配,那么应将选出的$a_i$和$b_i’$分别按照从大到小(或从小到大)排序,然后扫一遍,判断其是否满足这个等式即可。

但是如果这样的话复杂度就是$O((N-M+1)\times M)$(从长度为$n$中选长度为$m$的连续子数列有$(n-m+1)$种选法)

很明显,这个复杂度不够优秀。

那么我们可以用线段树来优化这道题。

令$b_1′ \ge b_2′ \ge b_3′ \ge \dots \ge b_m’$,则对于每个$b_i’$都应该有$\ge i$个$a$大于等于它。

所以,我们可以将$a,b’$离散化,对于每个$b_i’$,在线段树上的$b_i’$位置上减$i$,代表它需要$i$个数来大于等于它;对于每个$a_i$,在线段树上的$[1,a_i]$上加$1$,代表这些位置上的都比它小,为其产生贡献。

那么最后只要判断下线段树上是否每个点都是非负数即可。

注意,当两个$b_i’$相同时,只需要取$i$更的即可,不能叠加

那么,如何来判断线段树上是否每个点都是非负数呢?

只需要记录一个最小值,若最小值都大于等于$0$,那么肯定完全匹配。

所以,我们每次枚举一下区间,将$[1,a_{i-m-1}]$减去$1$,并将$[1,a_i]$加上$1$(移动区间),然后判断下最小值是否大于等于$0$即可。

复杂度非常优秀$O((N-M+1)\times logN)$

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇