只是为了说明这个做法正确。~~感觉有点无意义。~~
by LJ07 @ 2022-12-07 22:26:03
@[LJ07](/user/312306) 咋做啊，细嗦
by UnyieldingTrilobite @ 2022-12-08 13:40:01
这样会有给到相反数吧，归出来不是最大子段和么
by UnyieldingTrilobite @ 2022-12-08 13:40:48
@[UnyieldingTrilobite](/user/250637)
1. 二分然后 $1, -1$ 标号（大于等于赋 $1$，小于赋 $-1$），然后就是求是否存在一个区间 $[l,r]$ 满足 $l\in[a,b]$ 且 $r\in [c,d]$，使得区间和大于等于 $0$。
2. 众所周知区间和可以写成前缀相减形式，那么就相当于要 check $\max_{i=c}^{d} sum_i$ 是否大于等于 $\min_{i=a}^b sum_i$（这里 sum 即表示 prefixsum）。
3. 离散化后主席树。初始编号都是 1，有 $sum_i=i$。
4. 动态将指针向后移，若将 $pos$ 位置上的 $1\rightarrow -1$，就相当于将 $[pos,n]$ 的 sum 都减 $2$，标记永久化。
这样就做完了。
by LJ07 @ 2022-12-09 21:27:54
@[LJ07](/user/312306) 哦这个做法，那确实是可以的
by UnyieldingTrilobite @ 2022-12-09 21:28:50