poj 3294

和这题差不多，二分后后缀数组$height$判断，此题要输出所有的解，用个数组存下每个解在$a$中的起始位置即可。不同的是，此题判断时一定要找到一个$height[i]<x$或者循环完毕$height$才能更新解，这样才能防止重复解出现。
(ps: $vi$数组不要开大了，否则memset时容易TLE)

spoj 694

给出一个字符串，求字符串中不相同的子串个数。

我们可以知道，字符串中的每个子串都是某个后缀的前缀，于是题目转化为求不相同的后缀的前缀问题。对于每一个$SA[k]$开始的后缀，将会增加$n-SA[k]+1$个后缀，而其中$height[k]$个是和前面的字符串的前缀是相同的。所以答案就是所有$n-SA[k]+1-height[k]$的总和

hdu 2328

给出n个字符串，输出他们的最长公共子串，无解输出”IDENTITY LOST”

用不同的符号连接每个字符串，然后二分公共子串的长度，在$height$数组中看有没有连续$n$个$height$大于公共子串的长度，如果有，那么更新答案。
(此题暴力比SA快，而且poj上用SA一直TLE，Hdu上1840ms就过了)

poj 2774

给出两个字符串，求这两个字符串的公共子串。

我们可以连接两个字符串，中间插入$\$$，然后构造后缀数组，用$height$数组解决。

以abbbc和bbc为例。

因为后缀数组是字典序排的，所以排名最近的两个后缀拥有的最大公共前缀一定比不相邻的长。所以，由图可知，只要后缀$i$的位置在串1的范围，后缀$i-1$在串2的范围(反过来亦可)，那么就可以用$height[i]$更新$ans$的答案

BZOJ 4196

树链剖分支持修改查找子树和到根的路径权值和即可解决，注意pushdown放前面注意lc，rc会爆的情况

BZOJ 4034

树剖后线段树维护。
此题要修改子树的权，根据树剖性质子树是连续的一段，运用时间戳思想即可。

注意开long long，第一次没开就WA了(痛不欲生)

BZOJ 2763

分层图最短路

注意：priority_queue默认排序序列是从大到小的，所以重载小于符号时要a>b
以后权值一律写w，不要用v或c！

一、随机生成一个小于等于$n$的数

int RAND(int n) {
    srand((int)time(0)); 
    return rand()%n+1;
}

bzoj 1036

树剖+线段树。

第一个树剖题，终于AC

hdu 3666

由题意可知, $$L <= C(i,j) * a_i/b_j <= U$$
可以都除以$C(i,j)$, 得 $$L/C(i,j) <= a_i/b_j <= U/C(i,j)$$
此时都是除法，不满足差分约束

看两个性质
$log(a/b) = log(a) - log(b)$
$log(a*b) = log(a) + log(b)$

那么原式可以变为
$$log(L/C(i,j)) <= log(a_i/b_j) <= log(U/C(i,j))$$
$$log(L) - log(C(i,j)) <= log(a_i) - log(b_j) <= log(U) - log(C(i,j))$$
将$a_i, b_j$看做是一个元素，就可以建立差分约束系统求解是否存在