给定一个随机序列,每次给定4个随机操作
- 区间加一个数
- 区间置为一个数
- 求区间第$k$大值
- 求区间$[l,r]$里$\sum_{i=l}^{i=r} {a_i}^x$
由于是随机数列,所以可以将一个序列划分为一段一段的值域,对值域进行操作即可,也就是暴力,lxl把它称为$old~driver~tree$
复杂度:数据结构有一个$logn$,$oldd~river~tree$在随机数据下的均摊是$O(n)$的,总共是$O(nlogn)$,因为每次$add$操作不会改变区间值域的个数,$set$会推平很多区间,一个小区间最多被推平一次,每次询问最多多产生$2$个区间(相对于推平操作而言是很小的),在4个操作中,$\frac{1}{4}$的概率推平$O(n)$个区间,$\frac{2}{4}$的概率增加1~2个区间(询问),$\frac{1}{4}$的概率什么也不做。相当于每个区间访问$4$次就能删除(与其他合并)了,所以复杂度是$O(n)$的,再带上$set$的$log$,总共是$nlogn$
|
|