我们以如下问题介绍操作并尝试进行一个浅显的复杂度分析：
操作一：区间加
操作二：区间赋值
操作三：区间和
保证数据随机
操作：
珂朵莉树在处理时，将数组分成包含连续相同段的若干段，并用\(set/list\)维护，对区间\([l,r]\)操作时，暴力枚举区间内的段，并\(O(1)\)修改一个段。
复杂度:
我们令\(O(pred)\) 为找到区间内第一段的复杂度，并令\(d\)为表示区间内当前包含的段数，那么我们知道一次操作\(O(pred + d)\) (操作二与\(d\)无关)。
从段数分析，操作一使段数增加\(O(1)\) 个，操作二使总段数减少\(O(d - 1)\)。
Lemma 1.
若进行了 \(m\) 次操作，令随机变量 \(d_i\) 为第\(i\)次操作的段数，则\(\mathbf{E}[\sum_{i = 1}^m d_i] = O(n + m)\) ，即给出了忽略查询第一段操作后，我们的复杂度为\(O(n + m)\)
Proof
令随机变量\(f_i\)表示第\(i\)次删除的基本段数，那么有 \(\mathbf{E}[d_i] = O(\mathbf{E}[f_i] + 3)\) ,我们知道\(\sum_{i = 1}^mf_i \to O(n + m)\)
因为初始有\(O(n)\) 段，一次只会最多增加一个，而删除的段数不超过所有段数和，通过期望的线性性可以得证，\(\mathbf{E}[\sum_{i = 1}^m d_i] = O(n + m)\) ,事实上，通过直觉，我们很容易感知到这个结论。
Lemma 2
令\(p_j\) 表示了一个下标\(j\in{1,....,\ n}\) 的段的端点在经过\(m\)次操作二后的过程中始终为基本段的端点的概率，那么有\(\frac{1}{n}\sum_{i = 1}^n p_j = O(\frac{1}{m})\)
Proof
实际上等同于一个硬算的技巧。
Lemma 3
令\(t\)为总基本段，那么\(m\)次操作后期望为\(O(\frac{n}{m} + log\min({m,n}))\).
Proof
其为结论二的推论，其实只要求出基本段的端点总数从创建到最后存在的概率即可。
首段查询的复杂度
我们使用\(set\)维护
那么\(O(pred) = O(logt)\)
可得其期望复杂度为\(O(nloglogn)\)
本文大部分来自珂朵莉树的复杂度分析。
其在原文中还分析了线性做法。
#include<bits/stdc++.h>
#define ll long long
#define MOD7 ((ll)1e9 + 7)
#define mod9 ((ll)1e9 + 9)
#define N 100007
#define int ll
using std::set;
using std::vector;
using std::pair;
struct P{
int l,r;
mutable ll v;//该块的key
P(int L,int R = -1,ll V = 0):l(L),r(R),v(V){};
};
bool operator < (P a,P b){return a.l < b.l;}
set<P>s;//全部的块
inline set<P>::iterator split(int pos){
set<P>::iterator it = s.lower_bound(P(pos));
if(it != s.end() && it -> l == pos)return it;//刚好是一个块
-- it;
int L = it -> l,R = it -> r;
ll V = it -> v;
s.erase(it);
s.insert(P(L,pos - 1,V));
s.insert(P(pos,R,V));
return s.lower_bound(P(pos));;
}
inline void add(int l,int r,ll p = 1){
// std::cout<<"case1:"<<l<<" "<<r<<" "<<" "<<p<<std::endl;
set<P>::iterator li = split(l),ri = split(r + 1);
while(li != ri){
li -> v += p;
// std::cout<<"!"<<li -> l<<" "<<li -> r<<" "<<li -> v<<std::endl;
++li;
}
}
inline void cover(int l,int r,int p){
set<P>::iterator li = split(l),ri = split(r + 1);
s.erase(li,ri);
s.insert(P(l,r,p));
}
inline ll rank(int l,int r,int k){
set<pair<ll,int> >V;
V.clear();
set<P>::iterator li = split(l),ri = split(r + 1);
while(li != ri){
V.insert(pair<ll,int>(li -> v,li -> r - li -> l + 1));
++li;
}
set<pair<ll,int> >::iterator u = V.begin();
while(u != V.end()){
k -= u -> second;
if(k <= 0)return u -> first;
++u;
}
return -1;
}
ll pow(ll a,ll b,ll mod){
ll res = 1;
ll ans = a % mod;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
inline ll sum(int l,int r,int x,int mod){
// std::cout<<"case4"<<" "<<l<<" "<<r<<" "<<x<<" "<<mod<<std::endl;
set<P>::iterator li = split(l),ri = split(r + 1);
ll res = 0;
while(li != ri){
// std::cout<<"?"<<li -> l<<" "<<li -> r <<" "<<li -> v<<std::endl;
res = (res + 1ll * (li -> r - li -> l + 1) * pow(li -> v,x,mod) % mod);
res = (res >= mod) ? res - mod : res;
++li;
}
return res;
}
int n, m;
ll seed, vmax;
ll rnd()
{
ll ret = seed;
seed = (seed * 7 + 13) % MOD7;
return ret;
}
ll a[N];
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
for(int i = 1;i <= n;++i){
a[i] = (rnd() % vmax) + 1;
s.insert(P(i,i,a[i]));
// std::cout<<a[i]<<" ";
}
s.insert(P(n + 1,n + 1,0));
while(m -- ){
int op = (rnd() % 4) + 1;
int l = (rnd() % n) + 1;
int r = (rnd() % n) + 1;
if(l > r)std::swap(l,r);
if(op == 1)add(l,r,(rnd() % vmax) + 1);
if(op == 2)cover(l,r,(rnd() % vmax) + 1);
if(op == 3)std::cout<<rank(l,r,(rnd() % (r - l + 1)) + 1)<<std::endl;
if(op == 4){int x = (rnd() % vmax) + 1;std::cout<<sum(l,r,x,(rnd() % vmax) + 1)<<std::endl;}
}
}