主席树（可持久化线段树）权值线段树普通的线段树维护的是单点的值，比方说一个数组是{1,1,2,4,2,4,3,4}，开成普通线段树长这样 而权值线段树维护的是这个数出现了几次，就比方说上面的数组维护成了这样 主席树现在我们在树中插入一个数2 观察修改过后的权值线段树，发现只有红色的链有 ...

我使用的版本是NOI Linux 1.4.1 字体我主要安装的字体是 YaHei Consolas Hybrid 如何安装字体？请在执行以下操作时确定自己为根目录管理员（root），也可以通过终端完成操作。 在/usr/share/fonts/内创建 ...

动态树的一些操作：据说树剖能做的动态树都能做，但目前使（wo）用（zhi）最（xue）多（hui）的LCT不擅长处理子树操作（也有可能是我太菜了） 单点修改/询问 路径询问 连边/删边 ······ 模板12345678910111213141516171819202 ...

平衡树的一些操作： 查询x的排名 查询第x的数 查询x的前驱/后继 翻转给定区间 查询最大/最小的数 在某个位置插入x 在某个位置插入一串数 删除某个位置的x 删除某个位置开始的一串数 修改某个位置开始的一串数为x 查询区间和/本质不同的数值个数 将数x移 ...

树链剖分的一些操作： 查询子树范围 查询两点最短路径 求LCA ← 树剖LCA 最大子树 结合线段树可以做到： 修改单点值/子树/两点间的值 查询单点值/子树/两点间的和/最大值/最小值 ······ ······ 模板树剖 ...

12int ls(int x){return x<<1;}int rs(int x){return x<<1|1;} 线段树1区间加减，区间查询 1void push_up(int x){ans[x]=ans[ls(x ...

1234int lowbit(int x){ return x&(-x);} 树状数组1单点修改，区间查询。 12//需要先 add(i,a[i]); 123456void add(int x,long long d){ for(;x& ...

字符串的经典类型有一项为单串匹配问题，这是指一个模式串在一个文本串中出现了多少次并求出出现的位置的一个问题。我们称模式串长为$n$，文本串长为$m$，那么有 理论复杂度下界$O(n+m)$。 考虑暴力每次在文本串中的每一个位置从前往后匹配尝试是否正确。 对于随机数据来说十分优秀，甚至有 ...

gcdSTL库中有个template化的非递归版gcd，需要调用<alogorithm>使用方式是 1c=__gcd(a,b); 手写的话： 递归版： 1int gcd(int a,int b){return (!b)?a:gcd(b,a%b);} 非递归版： ...

LuoguT53818: Splay？Rotate？不不不！这些都是蒟蒻出题人吓唬做题人的道具而已。 实际上 rotate 操作在这里起到的作用等价于将节点的父节点染为相同颜色。原因就是在rotate(x)之后，x 的原父节点 y 的另一个儿子变成了 x 的后代，而 y 变成了 x 的后代。 ...