重生之 CF2126G2. Big Wins! (hard version)
$$ 高考结束了，前退役 \text{Oie} 要开始 \text{Ta} 的 \text{ACM} 生活了。$$前置：一个区间的 \(med \geq x\) 等价于若将 \(a_i \geq x\) 的元素赋值为 \(1\) ，其余赋值为 \(-1\) ，元素之和 \(\geq 0\)
本题没有限制\(\text{ a}\) 的大小，也就是没有限制 \(med\) 的大小。第一个想法是枚举 \(\text{min}\) 值，对每一个 \(a_i = min\) 的位置用单调栈或者笛卡尔树计算能保持最小值的 \(l_i\) 和 \(r_i\) ，然后我们考虑这个区间内的 \(med\)，复杂度为 \(O(n^2 \log n)\) 。
我们考虑如果从小到大枚举 \(med\) ，依次更新每个 \(min\) 值对应的 \(med\) 看能否取到，很可惜，这样也只能做到 \(O(n^2 \log n)\)。
但是我们注意到，刚刚的对每个min求med是没有必要的，我们只是想知道他们的最大差值，那么我们不妨从小到大枚举每个\(min\)，并且在线段树中进行修改，对于同一个\(min\)，我们可以不断尝试让 \(med\) 增大，直到顶到上限。同时由于我们枚举的区间的 \(min\) 值不断上升，若想要更新答案，\(med\) 值必然要增大才会有可能更优，二者均单调递增，复杂度优化至 \(O(n\log n)\)
点击查看代码#include#include#include#include#include#includeusing namespace std;typedef long long ll;const int N=2e5+5;int T,n,a;vector pos;int al,ar;inline void read(int &x){ int f=1;char c; for(x=0,c=getchar();c'9';c=getchar()) if(c=='-') f=-1; for(;c>='0'&&c
页:
[1]