钦定一个区间中最左边的最小值起贡献。容易单调栈求出每个位置 $i$ 起贡献的区间 $[l_i,r_i]$。 先考虑简化版问题，即 $L=1$。考虑一个归并排序的过程，即先对于一个 $i$，把它起贡献的区间的权值从小到大排序，再把 $n$ 个数组归并。由于 $a_i$ 固定所以只需要对长度排序。我们对这些长度去重并记录出…

重链剖分 + 颜色段均摊，维护每种颜色 $v$ 出现次数 $c_v$ 和每种出现次数 $x$ 对应的颜色个数 $\operatorname{cc}_x$。插入、删除颜色段时两者的变化是好维护的。每次查询就是输出 $\operatorname{cc}_m$。 一共产生 $\mathcal{O}(Q\log n)$ 个颜色…

> 求长度为 $n$ 序列 $a$ 有多少个子区间的众数出现次数超过了区间长度的一半。$n,a_i\le 5\times 10^5$。 我们称在区间中出现次数超过区间长度一般的众数为绝对众数。显然，一个区间至多有一个绝对众数。因此枚举每种权值计算贡献。 记 $S_{x,i}$ 表示 $\sum\limits_{j=1}…

在文章《题解：P14588 [LNCPC 2025] 前线支援》发表评论：

Top trees @ 全国领先

有区间赋值操作考虑颜色段均摊。对每种颜色 $c$ 维护 $\operatorname{tag}_c$，再对每个位置 $i $ 维护一个 $b_i$，使得当前 $i$ 的真实值为 $b_i+\operatorname{tag}_{c_i}$，其中 $c_i$ 为 $i$ 当前的颜色。 对于一个颜色段 $(l,r,u)$，…

在文章《人生不过一场呼吸。呼吸不停，则生命与思考不止。》发表评论：

这样可以跑到 3.2 s

在文章《人生不过一场呼吸。呼吸不停，则生命与思考不止。》发表评论：

唐了，代码里有同一棵线段树对同一个区间连续执行两次操作，写了两次 modify，事实上这个双半群信息支持一起修改。或者说可以先合并修改，就只需要依次 modify 了

在文章《NOIP RP++》发表评论：

愿你的努力，终将被世界成功编译。

在文章《题解：P8203 [传智杯 #4 决赛] DDOSvoid 的馈赠》发表评论：

比较难泵，你这个是 recall + replace

写了个垃圾做法，看来我对 Many Moves 的理解还不够深刻。 从小往大扫时间。这个问题没有后效性，考虑 dp。 记 $y_{i,j}$ 表示时刻 $i$ 的第 $j$ 个音符所在位置，其中 $j\in \{1, 2\}$。注意到在第 $i$ 个时刻，为了完成要求，一定有一只手会移动到 $y_{i,1}$ 这个位置…

在文章《雨下整夜》发表评论：

我擦这么牛

在文章《我咋叕写挂简单题了。》发表评论：

错别字有点多

在文章《我咋叕写挂简单题了。》发表评论：

打错了，P 应该是 DS

这个题 800 吧。 > - 给你一棵 $n$ 个点的有根树，根为 $1$，边带权。每个点有点权 $a_i$，初始 $a_i=0$。记 $\text{dis}(x,y)$ 表示 $x,y$ 简单路径上的边权和。 > - $q$ 次操作： > - `1 x y`：对于 $x$ 子树内的点 $u$，$a_u\leftarr…

在文章《人生不过一场呼吸。呼吸不停，则生命与思考不止。》发表评论：

是的，

一开始没看到对于每个 $i=1,2,3,\dots,k$ 都要满足条件认为这是不可做题。 先考虑序列问题，容易列出状态转移方程，将其写成矩阵形式就是所有矩阵做 $(+,\max)$ 矩阵乘法。 那么一次询问相当于在树链查询矩阵积。重链剖分，直接硬上线段树维护区间矩阵积是 2log，但是注意到除了最顶上的重链之外，其余重…

楼房重建傻了，现在才知道这个静态问题是可以 1log 的。 > 给出长度为 $n$ 的序列 $h_1,\dots,h_n$，$q$ 次询问 $l,r,H$，求 $\sum\limits_{i=l}^r\max\{0,\min\{H,\max_{j=l}^ih_j,\max_{j=i}^rh_j\}-h_i\}$。强制在…

绝世难题。 ::::info[题意] 给出一个 $1\sim n$ 的排列 $a_1, \ldots, a_n$ 和常数 $k$，保证 $1 \le k \le n$。 共有 $q$ 次查询，每次查询给出区间 $[l,r]$ 和 $x$（保证 $1 \le l \le r \le n$ 且 $1 \le x \le n…

在讨论《求助》回复：

@[Shimarin1001](luogu://user/1417178) https://www.luogu.com.cn/record/248008785 过了。

在讨论《求助》回复：

数组开小了。

在讨论《论区间历史和半群优化》回复：

区间赋值本质是乘加，都是可以用矩阵乘法刻画的。

在文章《P14528 [BYOI R1] 雨后屋檐 题解》发表评论：

原来是这样吗

在文章《P14528 [BYOI R1] 雨后屋檐 题解》发表评论：

就是，这个题是否强制在线之间的差别只是一个主席树，感觉没什么必要

在文章《P14528 [BYOI R1] 雨后屋檐 题解》发表评论：

不是很懂这个可持久化的意义在哪里

这个题 800 吧。 $\mathcal{O}(nk)$ 做法其他题解写的已经很清楚了，这里讲怎么做到 $\mathcal{O}(n)$。 快进到我们需要求出每个点 $u$ 为根的子树内，到 $u$ 边数 $\ge k$（换根还要用到 $k-1$ 的信息）的点的个数以及路径的边权和。 以边权和为例。朴素的 dp 是转化…

在文章《题解：P14463 【MX-S10-T4】『FeOI-4』呼吸之野》发表评论：

max 是不是应该改成 min 啊，因为前面是 -

在文章《题解：P14426 [JOISC 2014] 稻草人 / Scarecrows》发表评论：

分块怎么你了

在文章《题解：P14468 [COCI 2025/2026 #1] 和谐 / Harmonija》发表评论：

好像还没跑过你这个，乌鱼了

在文章《题解：P14468 [COCI 2025/2026 #1] 和谐 / Harmonija》发表评论：

每条重链维护前缀矩阵积，再用线段树维护矩阵乘积，这样只有一条链需要在线段树上查询，就 1log 了

在文章《CSP-S 2025 游记》发表评论：

世界机器大神