简单（✓）数据结构求解

ningago @ 2023-07-11 21:20:09

by monstersqwq @ 2023-07-11 21:24:46

二维数点呗

by ningago @ 2023-07-11 21:28:34

@reveal 请问这个转化以后如何维护 ql\leq i\leq qr 的限制 qwq

by 王熙文 @ 2023-07-11 21:29:07

不是三维数点吗？

by 王熙文 @ 2023-07-11 21:38:47

转化成求 ql\le i\le qr\land l_i<ql \land qr<r_i 的个数（为 0 即满足），离线 cdq 分治即可。

by fzj2007 @ 2023-07-11 21:40:44

@王熙文 您这怎么 1log 啊（？

by fzj2007 @ 2023-07-11 21:41:45

@ningago

转化为求 ql\le i\le qr 且 ql\le l_i 的加上 ql\le i\le qr 且 r_i\le qr 的减去 ql\le i\le qr 且 ql\le l_i<r_i\le qr 的

by fzj2007 @ 2023-07-11 21:42:59

第三类可以令 l^\prime_i=\min(i,l_i),r^\prime_i=\max(i,r_i) 然后二维数点吧

by reveal @ 2023-07-11 21:43:22

考虑一个垃圾做法：计数 l_i<ql\land qr<r_i，然后在 ql 与 qr 上差分。

然后对 (l_i,r_i) 的前缀点集维护凸壳，前面的计数可以在数据结构上对 x,y 分别二分（因为两个都是单调的所以可以在同一个数据结构上二分）。

然后使用可持久化就可以在线了。

by ningago @ 2023-07-11 21:44:27

/kt

by 王熙文 @ 2023-07-11 22:29:41

@fzj2007 哦我傻了