关于这题

P2839 [国家集训队] middle

LJ07 @ 2022-12-07 22:25:42

为啥题解区清一色的lmax，rmax，却没人写类似区间修改的主席树？标记永久化一下就是板题啊。check只需要 PrefixSumMax - PrefixSumMin 就行了。。。这个世界好奇怪。

by LJ07 @ 2022-12-07 22:26:03

只是为了说明这个做法正确。感觉有点无意义。

by UnyieldingTrilobite @ 2022-12-08 13:40:01

@LJ07 咋做啊，细嗦

by UnyieldingTrilobite @ 2022-12-08 13:40:48

这样会有给到相反数吧，归出来不是最大子段和么

by LJ07 @ 2022-12-09 21:27:54

@UnyieldingTrilobite

  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 UnyieldingTrilobite @ 2022-12-09 21:28:50

@LJ07 哦这个做法，那确实是可以的

|