day1 上午

正睿青岛

线段树区间操作 log？证明：每层返回的点最多两个。

树状数组，二分：
找一个最小的i,s[i]>=x，s[i]为前缀和。

线段树，判断当前的左边区间是否满足，满足递归左边，不满足走右边（减去左边的s[i]）

树状数组要求满足区间减。

练习1：一棵树，每次可以修。改一条边的长度，每次询问两点之间的路径长度。

ans = dep[u] + dep[v] - 2 * dev[lca]
维护dep
求出dfs序，每次修改一条边，相当于子树内所有点的深度增加。
树状数组区间修改+单点查询。

欧拉序？

二维数点

二维离散化？
离线

求区间内不同数的个数：

pre[i]为a[i]上次出现的位置。
询问[l,r]就是询问l<=i<=r，pre[i]

YNOI2016镜中的昆虫？

HDU 6315

b是排列，所以$\sum c_i <= nlogn$

ci = ai/b[i]
d[i]是a[i]还要加多少，才能让c[i]加1。
那么维护d[i]，每次一段区间的a加1，那么就是d[i]一段区间的减1。d[i]维护最小值，及其位置，然后不断找到最小值，让c[i]加1。
复杂度$nlog^2n$

void update(){
    if (!min()) return ; // 判断当前区间有没有最小值小于等于0
    update(lson); update(rson);
}

while (min()) {
    update();
}

b不是排列：大于根n与小于根n分别考虑。
大于根n，修改次数不超过根n。

GSS3

CF914D

二分，线段树维护gcd。然后每次将区间分成两半，如果满足条件，一定有一半是满足条件的，另一半递归下去。如果中途两边都不对，那么就是答案错的。
求gcd，每次求都是gcd变小，按顺序求的过程，运行次数可能会变小。

UOJ 222

切入点：
1、区间包含共同点，查包含的区间。
2、枚举最小的区间，最大的区间 看是否合法。

枚举最大的，枚举最小的，查查 n^3
知道了最小区间，那么最长的就可以二分了 n^2logn
单调性，左端点往有移了，那么右端点也会移，所以nlogn

CF264E

每个点维护以它开头的最长长度。

二维线段树？

noip2017 列队

bzoj 4552

排序考虑01序列
升序降序考虑01序列，所以升序就是1放到后面，降序就是1放到前面。
如果是01
二分以个答案p，然后模拟，看这个是0/1，1那么大于，否则小于

http://noi.ac/problem/32
https://www.lydsy.com/JudgeOnline/problem.php?id=4552

猫树

区间满足可加性，没有修改。

前缀和->保证可减性
st表-> a'+'a = a,'+' = min,max,gcd...

线段树每个节点的标号为l+r，那么都是不同的。
根据二进制，找到l,r，迅速定位的节点。

tips：树形背包：中间两个for（卷积），如果将for只for到size的大小，那么复杂度是$O(nm)$

询问区间长度为k，信息只满足可加性。均摊O(1)
[1,3] [2,4] [3,5] ... [a, a+2]
询问每段的乘积，不能除。
将区间分成长度为k的 n/k 断，每段处理往左往右的乘积，每个区间都是跨过一个点，询问即可。

询问无包含关系，还是只有可加性。询问均摊O(1)
l1 < l2 < l3 ... < lk
r1 < r2 < r3 ... < rk
首先用从r1开始往前跑，跑到l1，处理除每个位置到r1的信息。
然后对于第二个l2可能小于r1，r2可能大于r1，那么从r1往右扫到r2，维护除所有的信息。
当到一个线段时，li可能大于了r1，那么重新以ri为当前的信息线（信息线，维护了这个位置往左往右的信息），往左扫处理到li的信息。
同样类似的，加入的线段如果跨过ri，就从ri往右扫，否则以新的r作为新的信息线。

每个点往前往后一共扫两次，所以复杂度O(n)，每次询问均摊O(1)。

主席树与可持久化线段树：
主席树：支持加减（区间加减）。
可持久化线段树：不能合并，

可持久化线段树应用：
二维数点：（离线：扫描线，到左端，就减去，有端，就加上）。强制在线，记录下到每个位置的线段树。

启发式合并：
小的往大的合并，每次合并翻倍。
finger search：
查两个节点d1,d2，查了d1，在查d2，如果复杂度为log(d2-d1)，那么支持finger search。
支持finger search的平衡树，那么启发式合并是$O(nlogn)$的，否则$O(nlog^2n)$
splay支持。

线段树合并：
时间
总复杂度nlogn，均摊log，剪枝：每次如果两个线段树中有一个或者两个为空，那么就返回。
均摊：每次不保证是log，总的是log
如果都是完全树，那么合并复杂度就O(n)。但是建树的时候，动态开点，所以建的很多情况都是一条链，所以复杂度会减小。
证明复杂度：假设开始时是nlogn个点，每次合并如果在这一层递归下去了，那么会少一个点，加一个点。
空间复杂度log