耗时 97min 这一块(((
考虑扫描右端点 rrr,求出 ∑l=1rmex(l,r)\sum_{l=1}^r\text{mex}(l,r)∑l=1r mex(l,r)。
我们开个桶,定义 BiB_iBi 为 rrr 之前最后出现 iii 的位置。于是 mex(l,r)≥i\text{mex}(l,r)\ge imex(l,r)≥i 的充要条件就是 minj=0i−1Bj≤l\min_{j=0}^{i-1} B_j\le lminj=0i−1 Bj ≤l。
然后随便整一下式子,发现此时答案为 ∑l=1rminj=0n−1Bj\sum_{l=1}^r\min_{j=0}^{n-1} B_j∑l=1r minj=0n−1 Bj 。
于是就变成了单点改,求全局前缀最大值之和。
这个直接做应该也可以,但是我们又发现一个很好的性质,修改的数一定为 rrr。
所以我们从右往左扫描 rrr,显然此时修改的值单调递减。每个点取个前缀 min\minmin 就转化成了后缀 chkmin\text{chkmin}chkmin,查询全局和。这个可以线段树二分实现。一个可行的做法是用线段树分别维护区间 min,max\min,\maxmin,max,分类讨论进行二分。有更好的方法踢我。
什么叫我线段树调了 70min?
代码很史,将就着看一下。
时间复杂度:O(nlogn)O(n\log n)O(nlogn)。