查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转可以先考虑离散化离散话后是$1～n$一般要求中位数可以:二分中位数$x$将区间中$<x$的赋值为$-1$,$\ge x$的赋值为$-1$若区间和为$0$,那么$x$就是中位数题目是要求左端点在$[a,b]$,右端点在$[c,d]$的序列的最大中位数区间$[b+1,c-1]$是必选的我们可以求$[a,b]$的最大后缀和$[c,d]$的最大前缀如果这三个部分的和大于零,那么当前二分的值是合法的这个一看就可以用线段树维护我们再来考虑$x$变成$x+1$会有什么变化：原来$<x$的还是$-1$原……