珂朵莉树原理

其原理在于运用一颗树（set，treap，splay......）其中要求所有元素有序，并且支持基本的操作（删除，添加，查找......）来实现区间压缩。

那么区间压缩的意义在于区间推平这是珂朵莉树的核心（如果没有这个操作实际上不一定需要这种算法）

ps：若保证有连续相等甚至递增的区间，也可以的（吧？)。

可想而知它的操作在于对区间的分裂和合并操作

（为什么？因为这样可以方便而快捷的区间推平）

珂朵莉树的实现

在众多树中因为set这个c++自带，所以决定选择它。

结构

一个node结构体——把它叫区间(已typedef long long LL)

struct node {     int l,r;LL v;//这里官方写法加了一个mutable，看个人写法     node(int L,int R,LL V):l(L),r(R),v(V){}     bool operator < (const node& o) const     {         return l<o.l;     } };

声明集合

set<node>s;

初始化

for(int i=1;i<=n;++i)     s.insert(i,i,val); s.insert(n+1,n+1,0);//见下面中it!=s.end()的前提

分裂

#define it_ set<node>::iterator it_ split(int pos) {     it_ it=s.lower_bound(node(pos));     if(it!=s.end()&& it->l==pos) return it;     --it;     int ll=it->l,rr=it->r;     LL vv=it->v;     s.erase(it);     s.insert(node(ll,pos-1,vv));     return s.insert(node(pos,rr,vv)).first; }

区间推平

void assign(int l,int r,LL val=0) {     it_ itl=split(l),itr=split(r+1);     s.erase(itl,itr);     s.insert(node(l,r,val)); }

如上。

栗例子

见cf896c

仅仅给出代码

#include <bits/stdc++.h> #define it_ set<node>::iterator // #define swap(X,Y) {int (tmp)=(X),(X)=(Y),(Y)=(tmp);} using 

                    

                        
关键字：