前：day5下午——可持久化数据结构

衢州

可持久化线段树

修改->新建。
记录根节点。

主席树，函数式值域线段树。
不需要离散化，可以建立值域为2^31的主席树。

Bzoj 1901

单点修改，区间k值。

bzoj 3196 二逼平衡树

线段树合并

结构相同，一半合并线段树。

merge(int a,int b){
    if (!a||!b) return a | b;
    //r = ++N; //加上这句——可持久化
    lc[r] = merge(la[b],lc[b]);
    rc[r] = merge(rc[a],rc[b]);
    up(a);
    return a;
}

永无乡

Arietta

一棵树，1为根，每个节点有一个值。m次操作，每次在以Di为根的子树中，值在[L,R]的可以任选一个点，每个点最多选T次，求最多选多少点。

n m 10000

网络流。
线段树优化建图 log^2
线段树合并优化建图 log

匹配 && 最多匹配：所以网络流。
S -> 力度 -> 音符 -> T

bzoj 3065 带插入区间K小值

平衡树套主席树。
无法旋转？
1、不用旋转的平衡树 替罪羊树。（fhq treap：split也不支持）
2、旋转 && 复杂度正确的平衡树 treap。

块状链表？

可持久化字典树

一般是 0/1 trie。
处理位运算。

bzoj 2741

区间询问最大子段异或和。强制在线。
子段：连续一段。

n 12000
m 6000

错误思路：
对每一位建立权值线段树，然后查询区间里有没有这一位的1，多少个。
错因：每一位独立处理，导致可能出现的1不在同一个数里。

bzoj 3217 ALOEXT

插入、删除、修改、询问区间次大值与区间内元素异或最大值。

重量平衡树套可持久化Trie树。

可持久化平衡树

SLT rope

超级文本编辑器

可持久化treap

可持久化可并堆

均摊不能可持久化。
均摊<期望<严格。

可持久化左偏树

k短路