例题 CF1156E
求$a[l]+a[r]=max \sum_{i=l}^r a[i]$的区间个数。每个$a[i]$不同。
考虑朴素做法,找出每个$a[i]$所控制的区间$[L[i],R[i]]$。
$l\in[L[i],i),r\in(i,R[i]]$ 枚举一端判断另一端是否存在即可。
选择在小的那个区间中枚举一个端点,在另外那个区间中查有没有对应的值。
这样子看上去是 $𝑂(𝑛^2)$ 的,实际上是 $𝑂(𝑛log𝑛)$ 的。
它的本质是在笛卡尔树上启发式分裂(代更新)。
一种分治的做法
处理$[l,r]$,处理$max(a[i])的i\in[l,mid]$,$a[L]+a[R]=a[i]$双指针去移动$L,R$。反之但是用$Set$维护即可。复杂度$O(n\log^2 n)$
例题 HDU6701
$max \sum_{i=l}^r a[i]- (r-l+1)<=k$且元素不重复的区间个数。
同样做法找出每个$a[i]$所控制的区间$[L[i],R[i]]$。
选择在小的那个区间中枚举一个端点,$a[i]-k<=(r-l+1)$
假设枚举$l\in[L[i],i]$,则最少到达就是$L=max(i,l+a[i]-k-1)$,并且预处理不重复元素每个元素的边界$[Lc[i],Rc[i]]$,此时最远到达就是$Rc[i]$,$ans=ans+min(Rc[i]-R+1)$
- $r\in [i,R[i]]$也一样。
- 注意由于元素相同,处理最大值的时候控制$L[i]$最远,$R[i]$最近,不然会出现重复计数。
CF1156E
1 |
|
HDU6701
1 |
|