珂朵莉树学习笔记

再不见 · 2020-02-10 16:14:30 · 个人记录

珂朵莉树(ODT)大致定义：用map/set把一个序列中相同的一段数字压缩成一个点。
由其定义可以知道珂朵莉树的适用范围：题目中必须有区间赋值操作且数据随机。

实现方式：

1.建树：

struct chthollyTree {
    map <int , int> s;  
};

在map 中我们只记录一段连续的数中最右边一个
没了。

2.基本操作
求下标为x的值

I int find(int x) {
    return s.lower_bound(x) -> second
}

将x位置分裂

inline void split(int p) {
  int pos = find(p);
  s[p] = pos;
}

由于有时候询问或修改的区间是在一个连续段中的，没有记录在map中，所以在对其进行操作之前要提取这个区间[l,r]

#define it map<int,int>::iterator
inline pair<it , it> range(int l,int r) {
    split(l - 1) , split(r);
    return make_pair( s.find(l - 1) , s.find(r) );
}

修改某个区间(区间加)

pair <it , it> border = T.range(l , r);
st = border.first , ed = border.second;
while(st != ed) ed -> second += x ,  ed -- ;

计算某个区间的一些东西

int nxt;
for(ri i = l ; i <= r ; i = nxt + 1) {
    it now = T.s.lower_bound(i);
    nxt = min(r , now -> first);
    //calc...
}

例题

BZOJ4592
CF986C
洛谷P2572(本题被洛谷卡了，BZOJ上能过)