[肝学习资料]数据结构

前言

看学习资料啦啦啦
以下基本是口胡题解和一些想法总结。

花园

n个节点的树，m个操作，修改一个点权或者询问一条路径上某个权值的出现次数。
n,m<=10^5，点权在int范围，强制在线。

一开始想的炒鸡复杂。其实思路和数树数差不多。
对每个权值开线段树维护，然后转化为简单的求和问题，每个节点保存到根的和即可。由于权值在int范围内，不能直接开root数组，我们可以用map或hash。

kinoman POI2015

有一个长度为n的序列。选择一个区间[l,r]获得价值是 ∑ri=lwfi∗[fi在区间[l,r]仅出现一次]

枚举右端点，然后需要得到最大价值的区间。
枚举到i，显然可由i-1推来。
如何快速找到一个位置后第一个出现某权值的位置，可以用数组保存。
得到这个数组就是每个权值开线段树咯。

gty的游戏

不错的题目，做过了。
gty的游戏

楼房重建

有n条线段(i,0)-(i,hi)
m次操作每次修改一条线段长度，并要求你输出该次操作后从（0,0）可以看到的线段数量。

第i条线段可以被看到是什么情况？其顶端点与原点的连接线段的斜率在1~i中最大。
于是线段树维护区间最大斜率，每次二分答案判定即可。

peaks

做过，有在线做法，不会，感觉就是按照离线做法那样，加一些可持久化罢了。
peaks

序列游戏

有一个初始全0的长度为n的序列，m个操作，要么每次将[l,r]依次加上a%b,2a%b……(r-l+1)a%b，要么询问区间和。

我们先看如何计算 ∑ni=1AimodB
看到模要想到一个东西 amodb=a−⌊ab⌋∗b
于是转化为

∑i=1nAi−⌊AiB⌋∗B

n∗(n+1)2−B∗∑i=1n⌊AiB⌋

设后面那个东西是solve(A,B,n)
当 A>B 时，显然可以让A%B,并直接计算多余部分。
那么现在 A<B 了！我们也把规模缩成了solve(A%B,B,n)

∑i=1n⌊AiB⌋

∑i=1n∑j=1⌊AnB⌋[AiB>=j]

交换一下主体并进行一些不等式变换

∑j=1⌊AnB⌋∑i=1n[jBA<=i]

计算可以转化为全部剪去补集

∑j=1⌊AnB⌋n−∑i=1n[jBA>i]

前面的可以直接得到，后面那个东西显然等于 ⌊jBA⌋−[A|jB] ，减号后的可以通过分解质因数算出满足条件时j必须包含的因子（其实就是找出最小的满足条件j，那么j的倍数都符合条件）。
那么 ∑⌊AnB⌋j=1⌊jBA⌋ 可以递归运算，其就是 solve(B,A,⌊AnB⌋)
那么每次都从(A,B)变成(B,A%B)，这其实是一个类欧几里得算法，复杂度与欧几里得算法一致。

会算和了后，就可以线段树维护了。
然而线段树维护很慢，计算需要一个log，线段树又使用一个log。
可以考虑使用平衡树维护，平衡树每一个节点表示被覆盖的一个区间，那么每次加入一个新区间：
1、其本一个原区间覆盖，把这个原区间分成3部分。
2、其不被任何原区间覆盖，那么把其覆盖的原区间直接删掉，在与原区间交的部分建新点。
这样复杂度就降为一个log了！

Xor CF620F

定义f(x,y)为x~y之间所有正整数的异或和。
现有m个询问，每次询问所有l<=x<=y<=r中满足ax<=ay的f(ax,ay)的最大值。

注意到f(ax,ay)=f(0,ax-1) xor f(0,ay)
因此可以预处理异或前缀和。
建出两个trie，分别表示每个ai做为大数或小数时，做为小数时按照f(0,ai-1)插入，做为大数时按照f(0,ai)插入。
trie上每个节点保存对应ai的最大值和最小值。
那么插入一个新数，分别在两个trie上走一下，优先走和该为异或为1的边，检验能否走就是看最大（小）值是否（不）超过新数的a。
于是我们就知道了如何兹瓷插入一个数的维护。

接着将所有询问按照左端点分块，块内按照右端点排序。
接着一块一块的做，每一块内枚举右端点往右，当右端点超过该块右界时，要插入进trie中。也就是实时维护r+1~i的元素组成的trie，r为块的右界。
当枚举的i对应着询问时（即存在询问的右端点为i），如果右端点还在块内，直接暴力算出这个询问。否则，我们要将块内的剩余元素“暂时”加入trie中，可以理解为进行可持久化，做完后删除新增版本。
于是就解决了。

V 清华集训

需要你维护序列：
1、区间加法
2、区间赋值
3、区间变成max(ai-x,0)
4、单点询问值
5、单点询问历史最大值

我们可以用一种标记表示三个修改操作：x变成max(a+x,b)，设这个标记为(a,b)
如果x要加上a标记为(a,inf)
如果x要变成a标记为(-inf,a)
如果x要变成max(x-a,0)标记为(-a,0)
然后标记是可以合并的，合并(a,b)与(c,d)即
max(max(a+x,b)+c,d)
max(max(a+c+x,b+c),d)
max(a+c+x,max(b+c,d))
所以变成了(a+c,max(b+c,d))
然后就可以维护单点信息。

接下来解决历史最大值，观察标记，把x当做自变量就是一个分段函数，由常数函数与一次函数两部分组成。两个标记图像合并（这里的合并是取最大值）后图像仍然是一个模样。
因此可以维护这个分段函数，也就是维护“历史最大标记”，每当标记被更改时与历史最大标记进行合并即可。

玄学

给一个序列a以及q次操作，要么是一个修改操作，将[l,r]内的每一个ai修改为a*ai+b，要么是询问操作，询问在执行[l,r]的修改操作后ak的值。

可以考虑扫描线。把修改操作两端点以及询问操作的位置放在一起排序然后扫描。
以修改操作序列建线段树，区间维护执行完对应所有修改操作后一次函数的系数。
如果扫到修改操作左端点，加入到线段树中，扫到右端点即删除。
扫的询问操作直接在线段树里询问。
因为两个一次函数相加一定还是一次函数或常数函数（简要写就是可以写作y=ax+b），因此可以区间合并。

END

完结撒花