起源
给定一个序列$a_i$，长度为$n(n \le 10^5)$
有$m(m \le 10^5)$次操作
1 l r x$\forall i \in [l,r],a_i \leftarrow a_i + x$2 l r x$\forall i \in [l,r],a_i \leftarrow x$3 l r x输出$[l,r]$的第$k$小，保证$1 \le x \le r-l+1$4 l r x y输出$(\sum\limits_{i=l}^{r}a_i^x) \text{ mod } y$保证数据随机
看起来不可做的样子实际上真的不可做，不过由于数据随机生成，那么会有一些神奇的性质
看起来和 Segment tree Beats! 一样毒瘤
怎么做呢
ODT的核心思想是推平，即区间赋值所以为什么不叫Bulldozer Tree呢
以下翻译自ODT的题解
我们可以发现，有一个操作可以使得一段区间里所有数字都相同（即操作$2$）
我们可以用一棵平衡树（比如说std::set）来维护每一个数字都相同的区间
对于操作$2$，我们可以删掉平衡树上$[l,r]$中的所有的区间，并且添加一个新的区间$[l,r]$到平衡树上
比如说原先平衡树上有$[1,2],[3,3],[4,5]$，现在要删掉$[3,4]$，那么平衡树上的区间变成了$[1,2],[3,4],[5,5]$，当然要实现一个split操作，来诸如$[4,5]$这种区间
对于操作$1,3,4$，我们可以暴力的在树上提取出这些区间，然后在上面操作
时间复杂度证明我们假设现在随机的选取了一个区间$[l,r]$，之后我们随机的选择一个操作，假设当前平衡树上$[l,r]$中有$x$个区间
$\frac{1}{4}$的概率我们用$O(x)$的时间去删除$O(x)$个节点
$\frac{2}{4}$的概率我们用$O(x)$的时间苟着
$\frac{1}{4}$的概率我们用$O(x)$的时间苟着，并相平衡树添加两个新节点所以我们期望用$O(x)$的一件去删除$O(x)$个点
在用平衡树维护的同时，这道题的时间复杂度是$O(m \text{log} n)$
如果操作$3$和操作$4$变为输出$\sum\limits_{i=l}^{r}a_i$，那么时间复杂度看起来变为$O(m \text{log} \text{ log} n)$，但我不会证……
然而为什么一定要用std::set实现，如果序列长度下降的很快的话，直接用数组就行了
所以我选择用std::set实现
胡乱看一看推平操作的推平区间长度的期望是多少，即从序列中随机取出一个子区间的长度的期望
区间总个数为（即长度为$1$、长度为$2$等区间的个数和）
$$
T=n+(n-1)+(n-2)+ \cdots + 1=\frac{n(1+n)}{2}
$$
长度的期望为
$$
E=\frac{n }{T} \times 1 + \frac{n-1}{T} \times 2 + \cdots + \frac{(n-(n-1))}{T} \times n
$$
$$
ET=n \times 1 + (n-1) \times 2 + \cdots (n-(n-1)) \times n
$$
$$
ET=n + 2n + 3n + \cdots + n \cdot n - (1 \times 2 + 2 \times 3 + \cdots + (n-1)n)
$$
$$
ET=\frac{n^2(1+n)}{2}-(1 \times (1 + 1) + 2 \times(2+1) + \cdots + (n-1) \times ((n-1) + 1))
$$
$$
ET=\frac{n^2(1+n)}{2}-(1^2 + 2^2 + \cdots + (n-1)^2) - (1 + 2 + \cdots (n-1))
$$
$$
ET=\frac{n^2(1+n)}{2}-\frac{(n-1)((n-1)+1)(2(n-1) + 1)}{6}-\frac{(1+(n-1))n}{2}
$$
$$
ET=\frac{n^2(1+n)}{2}-\frac{n(n-1)(2n-1)}{6}-\frac{n^2}{2}
$$
$$
E\frac{n(n+1)}{2}=\frac{n^3}{2}-\frac{n(n-1)(2n-1)}{6}
$$
$$
E=\frac{3n^3-n(n-1)(2n-1)}{3n(n+1)}=\frac{3n^3-n(n-1)(2n-1)}{3n(n+1)}
$$
$$
E=\frac{n(n^2+3n-1)}{3n(n+1)}=\frac{(n+1)(n+2)-3}{3(n+1)}=\frac{n}{3}+(\frac{2}{3}-\frac{3}{n+1})
$$
$$
E \approx \frac{n}{3}
$$
也就是说推一次就合并了$\frac{1}{3}$左右的区间咯？看起来的确是log级别的大概
实现
本身就是直接暴力$\cdots$
两道例题
- codeforces 896 C
- codeforces 915 E
