珂朵莉树/颜色段均摊学习笔记

珂朵莉树是基于set的数据结构，与线段树、平衡树等树形结构类似，珂朵莉树是用来解决区间问题的很暴力的树形结构

该数据结构支持区间推平，即将区间\([l,r]\)赋值为同一个值

1. 前置知识 set

set本质是平衡树，所以不会出现重复的元素且会自动排序，部分函数：

set <Node> t;            //定义一个名为t，类型为Node（结构体）的set
s.begin();               //返回指向第一个元素的迭代器（地址）
s.end();                 //返回指向最后一个元素的迭代器
s.clear();               //清空s
s.insert(a);             //将a插入到s
s.erase(l,r);            //将迭代器l~r之间的元素全部删除
s.lower_bound(a);        //二分查找a在s中的位置，返回一个迭代器。
set<Node>::iterator pos; //定义一个迭代器pos。

2. 构造