2026 年 2 月日祭（梦熊集训）

梦熊集训是什么打板子大赛吗。

记录的题目跳过了一些板子。

Day 1 : 分块思想 & 莫队

其实这天是 1 月 31 日。

分块是会的，莫队是不会的。后者是，对于一些静态问题，若支持增删点，那么可以处理所有询问。具体地，按照询问左端点所属块的编号为第一关键字，询问右端点为第二关键字，对所有询问排序并依次处理。考虑分析时间复杂度，两个询问之间，左端点只会移动次；对于左端点所属块的编号相同的询问，右端点总共只会移动次，而块数是的。所以总时间复杂度是。

一个经典 trick 是，对于一些题目，我们需要增删点并查询，但或难以通过，此时需要考虑换一种数据结构维护答案。我们要求修改是的，但查询允许达到，而这恰好就是分块。对于这类问题，用分块维护就能够与莫队的时间复杂度平衡。

C - 教主的魔法

考虑分块。区间加是容易的，直接做即可。查询是困难的，考虑有什么东西能够维护这东西，容易想到排序与二分，实时维护对每个块排序的结果即可。时间复杂度或。
D - Range Set Query

区间数颜色，可以莫队草过。考虑做法，显然先离线下来，发现对于右端点，左端点的答案从右往左显然是单调不降的，而能带来贡献的点的颜色一定没在右侧出现。所以拿树状数组维护维护每个位置的贡献即可。
E - Range Shuffle Query

使用经典 trick 即可。
G - 异或序列

类似于小 Z 的袜子，直接莫队即可。
H - 弹飞绵羊

经典分块维护动态树。
I - 蒲公英

经典分块维护众数，以块为单位，预处理出每个区间的众数与每个元素在前缀的出现次数，那么每个询问的答案要么是零散块中的数，要么是整块的答案，随便处理一下即可。
J - 由乃打扑克

经典题，类似于教主的魔法，在外面再套一层二分即可，需要卡常。

Day 2 : 线段树进阶 1

这是线段树基础吧。

B - Takoyaki and Flip

需要维护加、翻转、清零的标记，注意一下几个标记的优先级与下放顺序即可。
C - Transformation

大概是屎吧，大力维护一下即可，不想写。
D - 大魔法师

直接做是困难的，发现只有矩阵能维护这东西，然后做完了，需要卡常。
F - Maximize The Value

对于每个元素单独考虑，发现此时只用维护一下最大子段和。扫描线即可。
G - 火灾 / Fire

感谢这道题占掉了我一下午，不然没事干了。

考虑初始每个数最终在矩阵上的覆盖区域。发现是一个平行四边形，它的长宽可以单调栈求出。平行四边形是困难的，将其拆成三个三角形，发现这三个三角形都是等腰直角三角形且有一条直角边在轴（）上。考虑询问，线段是困难的，射线是容易的，将一条线段拆成两条向左的射线。令三角形按右上角定位，射线按端点定位。考虑一个三角形对一条射线的贡献，可以分成两类。若三角形在射线左侧，那么三角形的贡献可以放到轴（）上，是一个带权的加；否则，三角形的贡献可以斜着（向左下）放到轴上，也是带权的加。把所有三角形和射线按位置排序，用两个树状数组（或线段树）维护两侧的三角形的贡献即可。

Day 3 : 线段树进阶 2

B - Rmq Problem / mex

主席树或莫队即可。
D - Clearance

简单的势能分析题。
E - DZY Loves Colors

好像不太熟悉有关颜色段的势能分析。考虑线段树维护，查询是容易的；对于修改，若当前区间颜色不同，那么暴力递归处理儿子；否则直接修改。考虑一次修改覆盖的区间，除了两侧可能有个零散的颜色段，中间的颜色段都是完整的，而一个颜色段只会被插入一次删除一次，插入和删除的时间复杂度是，所以总时间复杂度是。
F - 市场

经典势能分析题，维护并讨论极差即可。
G - 楼房重建

经典 trick，合并即可。