线段树入门
2026-10-26 20:30:12
发布于:广东
大家好,我是 Piggod,notch 说让我讲一篇线段树入门,讲了将给我 6767676767 dollar。
题单:https://atcoder.jp/contests/aalc001
3,2,1。
A
线段树板子,没啥好讲的。
B
注意到 运算是可以合并的,上懒标记线段树即可。
C
考虑在线段树里面二分。
只说询问 。当前区间为 的时候,如果答案加 还不会超,那就递归右儿子;否则递归左儿子。
。
D
维护:
- 为区间内 的个数。
- 为区间 , 的方案数。
显然可以线段树维护。
答案即为 。
时间复杂度:。
如果值域再大一点,开 个节点会 MLE,那咋办?
可以离线下来所有询问,扫 遍,第 遍只维护 。时间复杂度不变。
E
维护区间内 R G B RG GB RGB 的答案。
,。
F
最长连续段板子。维护区间左端点开始最长连续段,右端点开始最长连续段,然后随便判判即可。
时间复杂度:。
G
维护 ,然后二项式展开推一个特别史的式子即可。
时间复杂度:。
未完待续。
全部评论 2
dsa
1周前 来自 浙江
0d
1周前 来自 广东
0d
1周前 来自 北京
0



















有帮助,赞一个