脚本宝典收集整理的这篇文章主要介绍了线段树学习笔记，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
1. 复杂信息维护
- 「Luogu6327」区间加区间sin和
- 题意：
给定序列 (a_1,a_2,...,a_n)，支持两种操作：
- 给 (l le x le r) 的所有 (a_x) 加上 (k)。
- 查询 (sumlimits_{i=l}^{r}sin(a_i))。
(n,mle 10^5)
- 做法：
维护 (sin) 和还有 (cos) 和就行。
理由是下面这俩柿子：
[begin{aligned}sin(alpha+beta)=sinalphacosbeta+cosalphasinbeta\cos(alpha+beta)=cosalphacosbeta-sinalphasinbetaend{aligned}
]
所以：
[begin{aligned}sumlimits_{k=l}^{r}sin(a_k+c)=sumlimits_{k=l}^{r}(sin a_kcos c+sin ccos a_k)=cos c(sumlimits_{k=l}^{r}sin a_k)+sin c(sumlimits_{k=l}^{r}cos a_k)\
sumlimits_{k=l}^{r}cos(a_k+c)=sumlimits_{k=l}^{r}(cos ccos a_k-sin csin a_k)=cos c(sumlimits_{k=l}^{r}cos a_k)-sin c(sumlimits_{k=l}^{r}sin a_k)end{aligned}]
- 「CF1149C」Tree Generator™
- 题意：
给你一颗树的括号序列，求其直径。
然后 (m) 次询问，每次交换两个括号，求交换后的直径。
保证交换后的序列合法。
(n,mle 10^5)
- 题解
- 「CF1114F」Please, another Queries on Array?
- 区间修改：(a_i=a_itimes c,iin[l,r])。
- 区间询问：(varphi(prodlimits_{i=l}^{r}a_i)mod (10^9+7))。
(nle 4times 10^5,qle 2times 10^5)
2. 需要脑洞的题目
- 「HEOI2016 or TJOI2016」排序
- 题意：
将序列子段从小到大或从大到小排序,一共 (m) 次，最后查询位置 (q) 上的值。
(n,mle 10^5)
- 做法：
考虑 (01) 序列的排序如何实现。
我们发现 (01) 序列排序之后有一边是 (0)，一边是 (1)，所以给某个子段排序相当于两个区间覆盖操作，可以使用线段树维护
然后再考虑对于原数组 (a_i)，二分 (q) 位置上的最终值 (p)。将 (a_i<p) 的 (i) 标记为 (0) ，否则标记为 (1)。对于这个 (01) 序列排序，最后如果位置 (q) 上面的数是 (1)，就说明 (p) 一定比这个二分的值大。
- 「Luogu4198」楼房重建
嗝，咕咕咕
脚本宝典总结
以上是脚本宝典为你收集整理的线段树学习笔记全部内容，希望文章能够帮你解决线段树学习笔记所遇到的问题。
如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。