闲话
调全体T4
六点改出来了，但大样例不认为我改出来了
于是又花了两个小时修改不存在的错误
最近在做这题
[JRKSJ R4] risrqnis
想做主要是因为上琴糖
但是做着做着发现很神 而且我不会
请大家都来切一下（
所以写了珂朵莉树。
主要是因为复杂度的证明
和这题一样神奇
命は綺麗なわけじゃない
美しい人生なんてない
呼吸が上手く出来ないのは
生きてる証拠だ
关于颜色段均摊
又名珂朵莉树。
总而言之是一种通过均摊证出来的正确算法。特用于维护类似于区间改成一个值（或可以快速确定值）的操作。
具体有以下两种：
- 四种及以下操作，其中一个是 \([l,r]\) 赋值为 \(v\)。保证数据完全随机。
- 操作是 \([l,r]\) 赋值为 \(v\)。
先说1的做法。我们使用一个 set，其中每个元素记录 \(v\) 相同的区间 \([l, r]\)。set 的小于就按 \(l\) 小于重载，毕竟你得保证这里面的区间并是 \([1,n]\) 并且没有交。
#define IT set<node>::iterator
struct node {
mutable int l, r, val;
node(int lf, int rt, int v) : l(lf), r(rt), val(v) {}
bool operator < (const node & b) const
{ return l < b.l; }
};
set<node> s;
就这么写一下。set 的元素操作一般带一个 const 修饰，为了进行接下来的操作我们需要给元素上一个 mutable 保证能改值。记得把迭代器定义成好写的名字，因为一会儿得用很多次。
珂朵莉树的核心操作是分裂区间，即 \(split(pos)\) 函数。它会把 \(pos\) 所在区间 \([l,r]\) 分裂成 \([l,pos-1]\) 和 \([pos,r]\) 然后返回后一段。直接在 set 里查一下再处理就行。
inline IT split(int pos) {
IT it = s.lower_bound(node(pos, 0, 0));
if (it != s.end() and it->l == pos) return it;
it--; if (it->r < pos) return s.end();
int l = it->l, r = it->r, val = it->val;
s.erase(it);
s.insert(node(l,pos-1,val));
return s.insert(node(pos,r,val)).first; // insert返回一个 <iterator,bool> 的 pair
}
然后有了分裂就得有合并，即区间赋值函数 \(assign(l,r,v)\)。@brief This does what you think it does.
inline void assign_val(int l, int r, ll val) {
IT itr = split(r+1);
IT itl = split(l);
s.erase(itl, itr);
s.insert(node(l,r,val));
}
记得先 split 右边再 split 左边。因为左边 split 出来的迭代器可能会被右边 erase 掉，它可能指向一个非法地址。
然后有了区间赋值操作，剩下的东西就直接暴力就好。拿板子题CF896C说。show you the code：
区间加：
inline void add(int l, int r, ll val) {
IT itr = split(r+1);
IT itl = split(l);
while (itl != itr) itl->val += val, itl++;
}
区间 \(k\) 小：
struct rnks {
int num, cnt;
bool operator < (const rnks & b) const
{ return num < b.num; }
rnks(int nm, int ct) : num(nm), cnt(ct) {}
};
inline ll rnk(int l, int r, ll k) {
vector <rnks> vp;
IT itr = split(r+1);
IT itl = split(l);
vp.clear();
while(itl != itr) {
vp.push_back(rnks(itl->val, itl->r - itl->l + 1));
itl++;
} sort(vp.begin(), vp.end());
int pos;
for (pos = 0; pos < vp.size(); ++pos) {
if (k > vp[pos].cnt) k -= vp[pos].cnt;
else break;
} return vp[pos].num;
}
区间 \(p\) 次方和：
inline ll sum(int l, int r, int pw, int p) {
IT itr = split(r+1);
IT itl = split(l);
ll ret = 0;
while (itl != itr) {
ret = (ret + (itl->r - itl->l + 1) * qp(itl->val, pw, p)) % p, itl++;
} return ret;
}
然后证一下复杂度：
引理：在长度为1的区间内随机撒两个点，它们的间距为 \(\frac 13\)。
证：考虑积分。我们发现这个玩意的答案是
其中 \(D\) 为 \(x = 0, x = 1, y = 0, y = 1\) 围成的范围。然后进行一些初等的积分。
\[\begin{aligned} &\iint_D |y - x| dxdy \\ = &\ \int_0^1 dy \int_0^1 |y - x| dx \\ = &\ 2\int_0^1 dy \int_0^y (y - x) dx \\ = &\ 2\int_0^1 dy (\int_0^y ydx - \int_0^y xdx) \\ = &\ 2\int_0^1 dy (y^2 - \frac 12 y^2) \\ = &\ \int_0^1 y^2 dy \\ = &\ \frac 13 \end{aligned}\]因此由于数据随机，区间长度大致是 \(\frac n3\) 的（实际上期望是 \(\frac {n-1} 3\) 但需要一些离散和式的操作 麻烦不写）
定理：当有 \(\frac 14\) 的操作为区间赋值时，珂朵莉树内维护的区间数量的确界为 \(\Theta(\log n)\)。
不证，因为不会。
lxl说当有 \(\frac 13\) 的操作为赋值时有上界 \(O(\log\log n)\)。
也不会证。
例题：Willem, Chtholly and Seniorious
对于2情况，我们发现每个区间扔进珂朵莉树时只会增加 \(O(1)\) 个区间。每个区间花费 \(O(\log n)\) 的复杂度维护（split + assign），摊完复杂度是 \(O(n \log n)\) 的。因此直接维护就行，这里的复杂度一般不是瓶颈。
eazy round 真就 eazy 题 希望大家都能去切一下水题（
直接用珂朵莉树维护颜色段就行，每次加入删除连续段时对应地修改贡献，这部分的总复杂度是 \(O(n \log n)\) 的。