Limitの线段树题单 - 个人做题记录

Limitの线段树题单

https://www.luogu.com.cn/training/1124

纯萌新，渴望变强。

会不定期更新做题进度和一句话题解。

线段树入门

  • [x] P3372 【模板】线段树1
  • [x] P3373 【模板】线段树2
  • [x] P2023 [AHOI2009] 维护序列
  • [x] P1047 校门外的树
  • [x] P1276 校门外的数（增强版）
  • [x] P1531 I Hate It
  • [x] P5057 [CQOI2006]简单题
  • [x] P4588 [TJOI2018]数学计算

权值线段树

  • [x] P1908 逆序对

    典中典之 $\text{merge\_sort}$。

  • [x] P1637 三元上升子序列

    线段树查询 $[1,i-1]$ 中比 $a_i$ 小的数和 $[i+1,n]$ 中比 $a_i$ 大的数

  • [ ] P6186 [NOI Online 提高组]冒泡排序
  • [x] P3369 【模板】普通平衡树
    封装了 $\text{Splay}$ 的板子，在读入优化后，洛谷跑到了 $208\text{ms}$ ，感觉效率还行。

线段树进阶

  • [x] CF242E XOR on Segment

    考虑到数据只有 $2^{30}$，所以开 $30$ 棵线段树维护数字的每一个二进制位。

  • [x] P6492 [COCI2010-2011#6] STEP

    维护区间的最大长度，左边连续长度，右边连续长度，左段点类型，右端点类型。

  • [x] CF620E New Year Tree

    最多有 $60$ 种颜色，所以用一个 $64$ 位整形的数字去表示当前区间有多少颜色，同样类似状压的思想。

  • [x] P2894 [USACO08FEB]Hotel G

    数据水，写了个暴力过了。正解是类似 $\text{P6492}$ 的维护区间左右连续区间长度。

  • [x] CF438D The Child and Sequence

    区间取模问题。考虑到若一段区间的最大值小于当前模数，那么这一段区间在取模后还是自己，所以不操作直接返回。对于取模后会减小的部分暴力修改到根即可。在剪枝后成了优雅的暴力。

  • [x] CF240F TorCoder

    开 $26$ 棵线段树。这个区间中，出现的任何字母的出现次数要么都为偶数，要么只有一个奇数，其余都是偶数。优先把字典序小的字母放前面。

  • [x] CF431E Chemistry Experiment

    区间动态删减 , 维护有序的数组。记录子树内的节点数以及权值和，二分答案时记录子树外已经有多少节点数和权值和 , 计算补平需要多少。如果足够 , 就走向右子树 , 否则走向左子树。本题有线段树和树状数组解，我写的 $\text{treap}$ 。

  • [x] P2184 贪婪大陆

    维护 $[1,L-1]$ 中的终点个数和 $[1,R]$ 中的起点个数.

  • [ ] P1438 无聊的数列
  • [ ] CF992E Nastya and King-Shamans
  • [ ] CF1000F One Occurrence
  • [ ] CF1149C Tree Generator™
  • [ ] CF1422F Boring Queries
  • [ ] CF1004F Sonya and Bitwise OR
  • [ ] CF1114F Please, another Queries on Array?
  • [ ] P4145 上帝造题的七分钟2 / 花神游历各国
  • [ ] P6327 区间加区间 sin 和
  • [ ] CF446C DZY Loves Fibonacci Numbers
  • [ ] P1471 方差
  • [ ] P3300 [SDOI2013]城市规划
  • [ ] P4839 P哥的桶
  • [ ] P5142 区间方差
  • [ ] CF594D REQ
  • [ ] CF515E Drazil and Park
  • [ ] CF522D Closest Equals
  • [ ] CF739C Alyona and towers
  • [ ] CF718C Sasha and Array
  • [ ] CF383C Propagating tree
  • [ ] P2572 [SCOI2010]序列操作
  • [ ] CF803G Periodic RMQ Problem
  • [ ] CF911G Mass Change Queries
  • [ ] P4314 CPU监控
  • [ ] P4062 [Code+#1]Yazid 的新生舞会
  • [ ] P4247 [清华集训2012]序列操作
  • [ ] CF840D Destiny
  • [ ] SP1043 GSS1 - Can you answer these queries I
  • [ ] SP1557 GSS2 - Can you answer these queries II
  • [ ] SP1716 GSS3 - Can you answer these queries III
  • [ ] SP2713 GSS4 - Can you answer these queries IV
  • [ ] SP2916 GSS5 - Can you answer these queries V

动态开点

  • [ ] P5459 [BJOI2016]回转寿司
  • [ ] CF915E Physical Education Lessons
  • [ ] CF817F MEX Queries

扫描线

  • [ ] P5490 【模板】扫描线
  • [ ] P1856 [USACO5.5]矩形周长Picture

线段树合并

  • [x] P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
  • [ ] P3224 [HNOI2012]永无乡
  • [ ] CF600E Lomsat gelral
  • [ ] P3521 [POI2011]ROT-Tree Rotations
  • [ ] CF490F Treeland Tour
  • [ ] CF414C Mashmokh and Reverse Operation

线段树分裂

  • [ ] P5494 【模板】线段树分裂
  • [ ] P2824 [HEOI2016/TJOI2016]排序
  • [ ] CF558E A Simple Task

二维线段树

  • [ ] P3437 [POI2006]TET-Tetris 3D

吉老师线段树

  • [ ] P6242 【模板】线段树 3

树剖+线段树

  • [ ] P3384 【模板】轻重链剖分
  • [ ] P3178 [HAOI2015]树上操作
  • [ ] P4114 Qtree1
  • [ ] P1505 [国家集训队]旅游
  • [ ] P2146 [NOI2015]软件包管理器
  • [ ] CF343D Water Tree
  • [ ] P6157 有趣的游戏
  • [ ] P3833 [SHOI2012]魔法树
  • [ ] P3979 遥远的国度
  • [ ] CF877E Danil and a Part-time Job
  • [ ] P2486 [SDOI2011]染色

线段树优化建图

  • [ ] CF786B Legacy

TAG:none

发表新评论