-
P7811 [JRKSJ R2] 你的名字。
看到取模直接根号分治 设阈值为 ：离线后枚举每个 ，区间最小值随便做， 笔者直接大力分块 ：我们可以发现问题等价于求 只有 个，总询问个数 ，需要 查询最小值 我们考虑离线来降低查询复杂度，首先针对值域上的问题可以扫描线消一维，这个时候修改次数只有 ，可以从修改入手 我们把询问挂在值域上，然后从大到小扫，我们需要 区间最小值，这只有 RMQ 可以做到，但是我们知道 RMQ 不... -
莫队进阶
莫队基本思想： 根号级别移动完成区间统计，通常用于去掉区间一维限制，难度在于如何统计信息以及 修改，查询可到 级别，可以从这一方面根号平衡来优化 带修莫队[P1903 国家集训队] 数颜色 / 维护队列 修改 加入时间这一维度，每个时间都有一个 的数组，考察三维贡献 这里提一嘴高维莫队的基本方式，对前 维进行分块，最后一维暴力统计，复杂度 我们先讨论基本的三维莫队形式， 对前 ... -
23总结
我本来是不想写的，但这是作业 在去年的总结中，我给的四个形容词是：混乱，收获，思考，停滞。今年我我想用：迷茫，相信，哀叹，再次出发 这四个词来形容。 更加具体的陈述，这一年更像是摸索的一年，高考和竞赛的双重压力还是很有一点的，强行平衡两边。特别是上了高二9月份，联赛在即，压了大量时间在竞赛上面，每天睡的也晚，周末最早也要2点睡，完全是拿命顶。今年生病的次数可能可以超过前3年加起来（。 上半... -
分治进阶
Here’s something encrypted, password is required to continue reading.
-
Extra 线段树-线段树分治
线段树分治作为分治的一种主要用于有上下界的时效性的操作，而询问则是从 全部的这种 分治的核心思想就是将修改和询问丢一块，然后左右区间合并上来的时候考虑左边区间对右边区间的贡献，其修改一般都是永久性的，不可撤销，也就是作用时间是 线段树分治仅对询问区间进行分治，并且修改对应一段区间 ，也就相当于可撤销。进而，每个修改对应的就是一段询问区间。如果把询问建成 “ 线段树 “ 的模样，修改就... -
KD-Tree
Here’s something encrypted, password is required to continue reading.
-
可持久化并查集
Here’s something encrypted, password is required to continue reading.
-
树套树
Here’s something encrypted, password is required to continue reading.
-
平衡树进阶操作
[P5381 THUPC2019] 不等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 当我们发现一个点的大小不在是 的时候，但是求的东西可以转化为 ，也可以直接分裂 1234567void split_sz(int now,int size,int &l,int &r){ if(!now) return void(l=r=0); if(... -
Extra 线段树-线段树合并
线段树的高级用法 - qAlex_Weiq - 博客园 (cnblogs.com) 当需要开多个线段树，但是只需要维护一部分信息并要求合并线段树信息时，利用动态开点完成线段树合并 每次合并的复杂度是相同节点个数，每个节点至多被递归一次，总节点数在 级别 时空复杂度均在 级别 [P4556 Vani有约会] 雨天的尾巴 /【模板】线段树合并 - 洛谷 | 计算机科学教育新生态 (luogu...
