LuoguP2839 [国家集训队]middle

Description

题目链接

一个长度为 $n$ 的序列 $a$,设其升序排序之后为 $b$,那么序列 $a$ 的中位数定义为 $b_{\lfloor\frac{n}{2}\rfloor}$,其中 $a,b$ 从 $0$ 开始标号,除法取下整。

给你一个长度为 $n$ 的序列 $s$。回答 $Q$ 个这样的询问:$s$ 的左端点在 $[a,b]$ 之间,右端点在 $[c,d]$ 之间的子序列中,最大的中位数。

其中 $a<b<c<d$。位置也从 $0$ 开始标号。

强制在线。

$1\leq n \leq 20000,1\leq Q\leq 25000$。

Solution

首先对于每个询问,我们可以先二分答案。

考虑二分答案 $mid$ 如何 check。

如果我们将序列中的所有小于 $mid$ 的数字都标记为 $-1$,所有大于等于 $mid$ 的数字都标记为 $1$,那么我们只需要查询是否存在合法的一个区间内的和大于等于 $0$ 即可。

那么我们只需要先预处理建出选择所有 $mid$ 的值域线段树,这样每次相邻两个权值实际上只改变了几个位置,所以主席树即可,维护以下几个值:

  1. 区间和
  2. 区间最大前缀和
  3. 区间最大后缀和

那么合法的区间的最大值就是 $\max_{i=a}^{b+1}\sum_{i}^{b}+\sum_{b+1}^{c-1}{p_i}+\max_{i=c-1}^{d}\sum_{c}^{i}$。

用线段树维护即 $Rmax(a,b)+Sum(b+1,c-1)+Lmax(c,d)$。

所以我们只需要维护一下主席树即可。

Code

暂无评论

发送评论 编辑评论


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