P1076 · OFFICIAL SOLUTION

P1076 潮声四界定音官方题解

Gioush OJ · P1076 潮声四界定音

【部分分：测试点 1∼31\sim 31∼3】

原题为 P2839 [国家集训队] middle。
对一次询问，枚举 $l\in[a,b]$ 与 $r\in[c,d]$ 。复制子段 $x_l,\ldots,x_r$ 并排序，取上中位数。
一共有 $\mathcal O(n^2)$ 组端点，每次排序需要 $\mathcal O(n\log n)$ ，单次询问时间复杂度为 $\mathcal O(n^3\log n)$ 。
总时间复杂度为 $\mathcal O(qn^3\log n)$ 。这一步直接对应定义，也提示我们应先把“求最大中位数”改成判定问题。

【部分分：测试点 4∼74\sim 74∼7】

固定一个候选答案 $y$ ，把原序列转化为

b_i= \begin{cases} 1, & x_i\geq y,\\ -1, & x_i<y. \end{cases}

对任意非空子段，其中位数不小于 $y$ ，当且仅当子段内不小于 $y$ 的数不少于小于 $y$ 的数。
这正好等价于转化后子段和不小于 $0$ 。
每个合法子段都由三部分组成：

[l,b],\qquad [b+1,c-1],\qquad [c,r].

中间部分固定。左侧应选择 $[a,b]$ 的最大后缀，右侧应选择 $[c,d]$ 的最大前缀。
因此候选答案 $y$ 可行，当且仅当

\operatorname{Suff}(a,b) +\operatorname{Sum}(b+1,c-1) +\operatorname{Pre}(c,d)\geq0.

直接扫描三个区间即可完成一次判定，再二分 $y$ 。时间复杂度为 $\mathcal O(qn\log n)$ 。

【部分分：测试点 8∼118\sim 118∼11】

特殊性质给出 $a=b$ 且 $c=d$ ，左右端点都已经固定，询问变成求固定子段 $[b,c]$ 的上中位数。
对原序列建立值域可持久化权值线段树。第 $i$ 个前缀版本记录 $x_1,\ldots,x_i$ 中各离散值的出现次数。
用版本 $c$ 减去版本 $b-1$ ，即可得到子段 $[b,c]$ 的值域计数，再在线段树上寻找第

\left\lfloor\frac{c-b+1}{2}\right\rfloor+1

小的数。

时间复杂度为 $\mathcal O((n+q)\log n)$ 。

【部分分：测试点 12∼1512\sim 1512∼15】

设序列中不同的值为 $v_1<v_2<\cdots<v_V$ ，本档有 $V\leq50$ 。
对每个候选值 $v_j$ ，建立对应的二值序列，并建立一棵普通线段树，维护区间和、最大非空前缀和与最大非空后缀和。
对询问在 $v_1,\ldots,v_V$ 中二分，使用对应线段树完成三段查询与可行性判断。
预处理时间为 $\mathcal O(nV)$ ，询问时间为 $\mathcal O(\log V\log n)$ ，空间复杂度为 $\mathcal O(nV)$ 。

【正解】

线段树的每个结点保存

(\operatorname{Sum},\operatorname{LMax},\operatorname{RMax}),

分别表示区间和、最大非空前缀和、最大非空后缀和。

设左右儿子信息为 $A,B$ ，合并方程为

\begin{aligned} \operatorname{Sum}&=A.\operatorname{Sum}+B.\operatorname{Sum},\\ \operatorname{LMax}&=\max(A.\operatorname{LMax}, A.\operatorname{Sum}+B.\operatorname{LMax}),\\ \operatorname{RMax}&=\max(B.\operatorname{RMax}, B.\operatorname{Sum}+A.\operatorname{RMax}). \end{aligned}

若为每个候选值完整建立一棵线段树，空间会达到 $\mathcal O(nV)$ 。相邻候选值对应的二值序列只在少数位置不同，可以共享其余结点。
先建立阈值 $v_1$ 的版本，此时所有位置均为 $1$ 。
阈值从 $v_j$ 提高到 $v_{j+1}$ 时，恰好把所有满足 $x_i=v_j$ 的位置从 $1$ 改为 $-1$ 。
每次单点修改只新建根到叶子的一条链，其余结点沿用前一版本，这就是可持久化线段树。
全部阈值变化过程中，每个位置只会从 $1$ 变成 $-1$ 一次，所以总修改次数为 $n$ 。
建树与全部版本的总时间、空间均为 $\mathcal O(n\log n)$ 。
对固定版本，分别查询 $[a,b]$ 、 $[b+1,c-1]$ 、 $[c,d]$ ，取左区间最大后缀、中间区间和、右区间最大前缀。
若 $b+1>c-1$ ，中间区间为空，其区间和按 $0$ 处理。
随着阈值增大，序列中的 $1$ 只会变成 $-1$ ，可行性单调不增。
因此可以在离散值 $v_1,\ldots,v_V$ 中二分最大的可行阈值。每次判定需要三次线段树区间查询，时间为 $\mathcal O(\log n)$ 。
单次询问时间复杂度为 $\mathcal O(\log V\log n)$ 。
总时间复杂度为

\mathcal O(n\log n+q\log V\log n),

最坏可写作 $\mathcal O((n+q)\log^2 n)$ 。空间复杂度为 $\mathcal O(n\log n)$ 。

本题的完整链条是：最大中位数 $\longrightarrow$ 二分阈值 $\longrightarrow$ 正负序列 $\longrightarrow$ 最大合法区间和。
四个端点限制进一步把最大区间和拆成

\text{左侧最大后缀} +\text{固定中段和} +\text{右侧最大前缀}.

线段树只负责区间信息合并，可持久化只负责共享相邻阈值下未改变的部分。
上中位数的定义决定判定条件是区间和不小于 $0$ 。若改成下中位数，偶数长度时的判定边界也会随之改变。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/264Name:tonic.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 10001011#define MAXNODE 400001012using namespace std;13 14int T,n,q,cnt,ValueCnt,Line[MAXN],Root[MAXN],Mapping[MAXN];15pair<int,int> Ori[MAXN];16 17struct data{18    int Len,Sum,Pre,Suff;19};20 21struct node{22    int ls,rs,Sum,Pre,Suff;23}Node[MAXNODE];24 25data Merge(const data &A,const data &B){26    if(!A.Len) return B;27    if(!B.Len) return A;28    return {A.Len+B.Len,A.Sum+B.Sum,max(A.Pre,A.Sum+B.Pre),max(B.Suff,B.Sum+A.Suff)};29}30 31void Update(int Now){32    Node[Now].Sum=Node[Node[Now].ls].Sum+Node[Node[Now].rs].Sum;33    Node[Now].Pre=max(Node[Node[Now].ls].Pre,Node[Node[Now].ls].Sum+Node[Node[Now].rs].Pre);34    Node[Now].Suff=max(Node[Node[Now].rs].Suff,Node[Node[Now].rs].Sum+Node[Node[Now].ls].Suff);35}36 37int Build(int l,int r){38    int Now=++cnt;39    if(l==r){Node[Now]={0,0,1,1,1};return Now;}40    int Mid=(l+r)>>1;41    Node[Now].ls=Build(l,Mid);Node[Now].rs=Build(Mid+1,r);42    Update(Now);return Now;43}44 45int Modify(int Last,int l,int r,int Pos){46    int Now=++cnt;Node[Now]=Node[Last];47    if(l==r){Node[Now].Sum=Node[Now].Pre=Node[Now].Suff=-1;return Now;}48    int Mid=(l+r)>>1;49    if(Pos<=Mid) Node[Now].ls=Modify(Node[Last].ls,l,Mid,Pos);50    else Node[Now].rs=Modify(Node[Last].rs,Mid+1,r,Pos);51    Update(Now);return Now;52}53 54data Query(int Now,int l,int r,int Left,int Right){55    if(Left>r||Right<l) return {0,0,0,0};56    if(Left<=l&&r<=Right) return {r-l+1,Node[Now].Sum,Node[Now].Pre,Node[Now].Suff};57    int Mid=(l+r)>>1;58    return Merge(Query(Node[Now].ls,l,Mid,Left,Right),Query(Node[Now].rs,Mid+1,r,Left,Right));59}60 61bool Judge(int Version,int a,int b,int c,int d){62    data Left=Query(Root[Version],1,n,a,b);63    data Right=Query(Root[Version],1,n,c,d);64    int Sum=b+1<=c-1?Query(Root[Version],1,n,b+1,c-1).Sum:0;65    return Left.Suff+Sum+Right.Pre>=0;66}67 68void Solve(){69    int a,b,c,d;70    scanf("%d%d",&n,&q);71    for(int i=1;i<=n;i++){72        scanf("%d",&Line[i]);73        Ori[i]={Line[i],i};74    }75    sort(Ori+1,Ori+n+1);76    cnt=ValueCnt=0;77    int Now=Build(1,n);78    for(int i=1;i<=n;){79        int j=i;80        Mapping[++ValueCnt]=Ori[i].first;81        Root[ValueCnt]=Now;82        while(j<=n&&Ori[j].first==Ori[i].first){Now=Modify(Now,1,n,Ori[j].second);j++;}83        i=j;84    }85    while(q-->0){86        scanf("%d%d%d%d",&a,&b,&c,&d);87        int Left=1,Right=ValueCnt,Ans=1;88        while(Left<=Right){89            int Mid=(Left+Right)>>1;90            if(Judge(Mid,a,b,c,d)) Ans=Mid,Left=Mid+1;91            else Right=Mid-1;92        }93        printf("%d\n",Mapping[Ans]);94    }95}96 97int main(){98    int c;99    scanf("%d%d",&c,&T);100    while(T-->0) Solve();101    return 0;102}