P13242

rehtam · 2025-07-13 07:46:20 · 题解

赛时没写完的做法。

首先在满足条件的位置在后缀数组上一定是一段区间，转化为平面上有 n 个点 (i,p_i)，其中 p_i 为一个排列，每个点有点权 v_i= \displaystyle \min_{j=l}^{i} val_j，查询矩形和。

考虑离线怎么做。按照 l 从大到小扫过去，变为半平面 chkmin 矩形求和。可以用分块做到单根号。

强制在线的话可持久化即可，空间和时间都是单根号，需要卡一下空间。最慢点 2.57s。