数据结构题做题笔记
Karry5307
·
·
个人记录
Limit 是可爱的小姐姐/qq
为了练习数据结构于是就来写一下
P3372 【模板】线段树 1
这题随便写，就不咋说了。
P3373 【模板】线段树 2
还是随便写，只不过要注意的是乘法的标记下传的时候顺便要影响加法标记。
P6492 [COCI2010-2011#6] STEP
考虑将 L 记作 1，R 记作 0，再构造序列 b_i=a_i\operatorname{and}\ (l_i\operatorname{and}1)，那么 a 中一段交错子序列对应着 b 中一段 0 或是一段 1，那么只要维护一下这个东西的长度就好了。
这个的话就是跟 GSS 那个东西一样的，唯一有个不同的点（以维护最长的 0 前缀为例）就是如果只有左子区间全为 0 的时候才能让右子区间带来贡献。
P2023 [AHOI2009] 维护序列
板子题。
P1637 三元上升子序列
很明显 DP 一下，设 f_{i,j} 表示长度为 j 的子序列末尾在第 i 个的方案数，可以写出转移：
f_{i,j}=\sum\limits_{k<i,a_k<a_i}f_{k,j-1}
考虑从左往右枚举来解决 k<i 的问题，对于 a_k<a_i 可以离散化之后开权值线段树维护这些 f 即可。
CF915E Physical Education Lessons
因为出题人比较良心，所以这题变成了珂朵莉树模板题，没什么好说的。
P3384 【模板】轻重链剖分
板子题。
P5490 【模板】扫描线
咕咕咕。
P3369 【模板】普通平衡树
板子题。
P3833 [SHOI2012]魔法树
链加子树和，树剖板子题。
P2184 贪婪大陆
注意到对于某个询问 [l,r] 来说，如果区间 [l_i,r_i] 满足 l_i\leq r 那么这个区间还是有可能被计入贡献的，如果区间 [l_i,r_i] 满足 r_i<l 那么是不可能计入贡献的。
所以开两个树状数组维护一下满足 l_i\leq x 的区间个数和 r_i\leq x 的区间个数，然后直接减一下就好了。
注意这里是不会多减的，因为如果 r_i<l 的话那么 l_i\leq r 一定成立，就会在第一步加上去然后第二步减掉。
P3178 [HAOI2015]树上操作
板子题。
P2894 [USACO08FEB]Hotel G
咕咕咕。
P4145 上帝造题的七分钟2 / 花神游历各国
维护一下区间最大值，如果区间最大值为 0 或者 1 的话就不用修改这段区间，否则暴力递归。
因为一个数 n 开 O(\log\log n) 次平方就可以变成 1，所以时间复杂度可以保证。
P1438 无聊的数列
咕咕咕。
P4114 Qtree1
记录一下第 x 条边是什么就是个板子题了。
P4588 [TJOI2018]数学计算
不能直接做除法操作，因为模合数下有的数可能没有乘法逆元，那么考虑先把所有操作扔上来，然后撤销操作直接撤销，询问就是查询前缀积。
SP1716 GSS3 - Can you answer these queries III
老套路了，随便维护一下得了。
P2146 [NOI2015]软件包管理器
树剖板子题怎么这么多啊 >_<
P1471 方差
随便推一下式子：
ns^2=\sum\limits_{i=1}^{n}\left(\overline{x}-x_i\right)^2=n\overline{x}^2-2\overline{x}\sum\limits_{i=1}^{n}x_i^2+\sum\limits_{i=1}^{n}x_i^2
随便化一下
s^2=\frac{\sum\limits_{i=1}^{n}x_i^2}{n}-n\overline{x}^2
很明显要维护和和平方和，平方和的话懒标记的打法还是要推柿子：
\sum\limits_{i=1}^{n}\left(x_i+k\right)^2=\sum\limits_{i=1}^{n}x_i^2+2k\sum\limits_{i=1}^{n}x_i+nk^2
于是没了。
SP2713 GSS4 - Can you answer these queries IV
跟花神那题一样的。
CF343D Water Tree
树剖板子题。
P6327 区间加区间sin和
维护一下 \cos(a_i) 的和和 \sin(a_i) 的和，然后使用三角恒等变换：
\sum\limits_{i=1}^{n}\sin(a_i+t)=\cos t\sum\limits_{i=1}^{n}\sin a_i+\sin t\sum\limits_{i=1}^{n}\cos a_i
\sum\limits_{i=1}^{n}\cos(a_i+t)=\cos t\sum\limits_{i=1}^{n}\cos a_i-\sin t\sum\limits_{i=1}^{n}\sin a_i
这么样打懒标记就没了。
P1438 无聊的数列
这种 sb 题调了我好久，我真丢人。
考虑用两个懒标记记录首项和公差，然后利用等差数列求和公式：
\sum\limits_{i=1}^{n}a_i+k+(i-1)d=nk+\frac{n(n-1)}{2}d+\sum\limits_{i=1}^{n}a_i
然后没了。
P5142 区间方差
跟前面那个叫方差的题一个思路，但是没有浮点数的处理细节比较少。
SP1043 GSS1 - Can you answer these queries I
裸题。