所有标签

方法总结 #线段树

线段树专题总结

cover: Pixiv ID 99302008 本文重在记录线段树的各类应用技巧和各种相关问题，不会讲解线段树的原理及实现（当然也可以把这个看成一个大纲一样的东西，尽量做到每个板块由浅入深）。基础准备线段树是一个主要用于维护序列（或是集合）信息的数据结构，主要原理是预处理 O(\log) 个子

发布于 2026-01-10

Sol #dp #OOI #线段树

cover: 魔宴CG 首先简化问题很明显，每组有用的只有前缀最大值。先想想贪心，不可做，因为一组的贡献会被其他组影响，所以考虑 \texttt{dp} 组与组之间无序，不能沿编号轴 \texttt{dp} ,考虑值域轴，每接上一个组只需要考虑当前最大值，且较大最大值一定由较小最大值转移而来，所以

发布于 2025-10-24

Sol #COI #线段树

cover: Pixiv ID 138479350 你谷传送门非常 OI 的一道题看到这题就往图论的方向去想了，但其实能看出本质与竞赛图有关的话甚至能更快，只可惜事先没有接触过，敏感度不够。往正常方向推也挺好推的，但其实我在第一步就炸了，我考虑的是怎么利用整个排名表的信息维护一位选手的答案傻

发布于 2025-10-11

cover: Pixiv ID 138387115 题目传送门代码实现和一些思路参考了一些题解。遇到这种序列上研究大小的序列问题，应该主动考虑笛卡尔树。对原序列建出一棵大根笛卡尔树。稍微转化一下问题的连边条件，首先每个节点必定和它的左子树同在所有点在同一个连通块，这样初步连边后可以看出连通块与

发布于 2025-09-10

cover: Pixiv ID 70937229 From zxy的思维技巧而来。传送门这真是一道套路的好题啊。首先要计算二元组 (a,b) 的个数，看数据范围肯定枚举一个 a ，然后计算所有满足的 b ，最后求和后除以 2 。然后具体的考虑怎么计算所谓 b 的个数，考虑一个点

发布于 2025-07-18

cover: Pixiv ID 78486250 线段树真的是一种挺折磨人的数据结构，但它的应用范围也是非常广泛的。它可以在 O(\log n) 的时间内完成区间修改和区间查询。似乎有句话是这么说的：树状数组能做的，线段树都能做；线段树能做的，树状数组不一定能做。线段树的操作线段树是一种二叉树，

发布于 2024-08-22