警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P2839」middle - 主席树

题意

传送门:洛谷 P2839 - middle

给一个序列,每次查询两个区间 \([a,b],[c,d]\),最大化 \(l\in[a,b],r\in[c,d]\) 时,区间 \([l,r]\) 的中位数。

集合 \(S\) 的中位数定义为 \(S\) 中第 \(\lfloor|S|/2\rfloor+1\) 小的数。

\(1\le n\le2\times10^4,1\le q\le25000,a<b<c<d\),强制在线。

解法

神仙题。

令中位数为 \(x\)\(f(y)=\begin{cases}-1&y<x\\1&y\ge x\end{cases},g(l,r)=\sum_{i\in[l,r]}f(i)\)

如果 \(d\ge0\),那么中位数一定 \(\ge x\);否则中位数 \(\le x\)

然后就可以二分答案了。下面考虑如何写 check:

对于一个 \(mid\),我们要找到一个区间 \([l,r]\) 使得 \(g(l,r)\ge0\),即最大化 \(g(l,r)\)

因为 \((b,c)\) 这个区间是必须取的,所以对于每一个二分出来的 \(mid\),算出 \(g(b+1,c-1)\)

我们的目标是最大化 \(g(l,r)\),而 \(g(l,r)=g(l,b)+g(b+1,c-1)+g(c,r)\)

所以答案就是 \([l,b]\)\(f\) 的最大前缀和 + \(g(b+1,c-1)\) + \([c,r]\)\(f\) 的最大前缀和。这个可以用线段树维护。

我们先把数组离散化,那么答案的区间就缩小到了 \([1,n]\),然后对每个 \(i\in[1,n]\) 开一棵线段树,维护最大前缀和、最大后缀和、区间和。

注意到每棵树只会改一个数(本蒟蒻的实现没有去重,可以证明这样是对的),那么预处理的时空复杂度 \(O(n\log n)\)

查询需要二分,所以时间复杂度 \(O(n\log^2n)\)

代码

吐槽

这题题面的「子序列」真心误导人……