HEOI

题目链接：大工程 先考虑只有一次查询，很显然我们可以暴力树上 dp 处理出答案。 对于每个节点而言，有： 容易看出类似点分治逐个遍历子树计算前面一堆子树对后面子树的贡献思想，我们可以很容易的知道： 对于路径总和，显然多了一段新的贡献，这段贡献为当前关键点和前面点多的一段 \(2\) 号路线长。这段长 ......

题目链接：序列 对于 LIS 问题，很显而易见的有 dp方程为： \[dp_i=\max{dp_j}+1 \ (j<i,a_j \le a_i) \text{ dp表示以某个位置结尾的最长 LIS} \]本题考虑到对于转移的两位置，如果能从 \(j \rightarrow i\)，那么在以上条件成立 ......

李超线段树是一种用于维护平面直角坐标系内线段关系的数据结构，插入直线/线段，支持查询单点极值 李超树的经典应用是斜率优化，可以看下这篇文章 李超线段树没有用懒标记实现区间修改，而用的是标记永久化 其实标记永久化与我们对lazy标记的理解非常相同，可以看看LYD蓝书上对标记永久化的解释，都是累积某个节 ......

# [P2824 [HEOI2016/TJOI2016] 排序](https://www.luogu.com.cn/problem/P2824) 直接模拟复杂度爆炸，有观察到它只要求一个数。 思维十分清奇。 我们先考虑一个序列，如果全是 `0/1`，该怎么做。 发现这个问题很好做，修改区间时只需要先 ......

P4099 [HEOI2013] SAO 很有意思的一道题。 考虑树形 DP。首先考虑的是 \(f_i\) 表示 \(i\) 为根的子树内合法的拓扑序数量，但是这样合并子树的时候是无法计算的，如下图： 假设 \(1\) 当前合并了 \(3\) 这棵子树，接下来要合并红色和蓝色的部分，此时 \(2\) ......

针对区间排序，显然能够上值域线段树类似，但这里有个更强的做法。 如果能转化成01序列，那么一个区间排序的时候，只需区间询问1的个数+区间修改就可以了。 因为是排列，很清晰的二分一个mid，把大于等于它的设为1，小于它的设为0，再跑上面的算法，最后check一下询问位置是否为1即可。 单调性？感性理解 ......

题目链接 看到这道题按照套路首先想到二分答案（即二分 \(q\) 位置上的数，记作 \(mid\)）。 再按照套路将大于 \(mid\) 的数字设为 \(1\)，将等于 \(mid\) 的数设为 \(2\)，小于 \(mid\) 的数字设为 \(0\)。 那么对于区间 \([l,r,0]\) 操作， ......

原题(需要魔法) 原题(不需魔法) 强制在线做法 \(O(n \log n)\) 考虑每一次标记点：只会影响其子树中的点 所以使用DFS序+线段树就可以辣！ 离线做法 \(O(n \log n)\) 考虑将每一次标记的时间记录到点上 然后使用倍增 \(LCA\) 的思想向上倍增 离线做法 \(O(n ......

原题 今天我刚知道一个很逆天的事：\(DAG\) 的拓扑序方案数不可做！！!，目前能做到的最优方法好像是状压 我们考虑这题怎么做，对于一个限制，我们关心的是他俩在拓扑序中的相对排名，而这题恰好是一个树形结构，因此我们考虑树形 \(dp\) 我们设 \(dp_{i,j}\) 表示以 \(i\) 为根的 ......

RT 感觉会模板就差不多了，可用作处理一些线段或直线的问题，转化过来的也可以。比如DP的斜率优化，直线的话只用一个log,线段要两个log。 [[HEOI2013] Segment](https://www.luogu.com.cn/problem/P4097 "[HEOI2013] Segment ......

link：[[HEOI2015] 小 Z 的房间](https://www.luogu.com.cn/problem/P4111) ## 题意 你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含 $n\times m$ 个格子的格状矩形，每个格子是一个房间或者是一个柱子。在 ......

看到这种奇怪的操作，首先想到分块。 以下记值域为 $w$，块长为 $B$。 前缀 $\gcd$ 显然单调不增，而且后一个必须是前一个的因数，如果变化至少要减半。因此，我们知道，共有 $\mathcal O(\log w)$ 个不同的前缀 $\gcd$。我们可以接受对这些块暴力，只需要对前缀 $\gc ......

题目链接 题目 题目描述 萧芸斓是Z国的公主，平时的一大爱好是采花。 今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。 花园足够大，容纳了 $n$ 朵花，花有 $c$ 种颜色（用整数 $1-c$ 表示），且花是排成一排的，以便于公主采花。 公主每次采花后会统计采到的花的颜色数，颜色数越多 ......

P4093[HEOI2016/TJOI2016]序列 题目描述 佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。 玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一 ......

题目传送门 前言 线段树好题！！！！ 咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。 题意 给定一个 $1$ 到 $n$ 的排列，有 $m$ 次操作，分两种类型。 1.0 l r表示将下标在 $[l, r]$ 区间中的数升序排序。 2.1 l r表示将下标在 $[l, r]$ 区 ......

决定还是在博客园再发一遍。 省流：考试策略全部爆炸，时间分配全部爆炸，分数全部爆炸。 Day 0 去秦皇岛。路上一直在颓废。 车上打了会奥日，画风超美。 然后到宾馆之后接着打奥日，感觉还是这个比较适合我，~~太菜了打空洞打不明白~~ 晚上去领胸牌和巧克力，回宿舍颓一会睡觉。 躺下之后脑子里还挺乱的， ......

好像是被打破防了。 春季赛 春季赛忘的差不多了，但是总而言之打假赛。 day 0 去的是叫英庄李家的酒店，下午去看海了。手机在看到海并拍摄一张照片后残忍关机了。;) 晚上回酒店找人借充电线发现手机神秘地充不上电。好心的 char_phi 给我扫了个共享充电宝。 但是充了点电就交手机了。然后晚上看了看 ......

Day -inf 背景:NOIP 2022没考的高二退役选手 春季赛前同高一选手一起上奥赛课 春季赛考完不知道分但是好像能去省选 一开始我和bikuhiku都是拒绝的 但是一想不如去一趟 于是我们两个就都报上名了 (中间有个自习听到省选的消息的时候笑了一整节课) 中间放假问bikuhiku要不要奥赛 ......

「比赛游记」2023NOI 春季赛 & HEOI 游记 点击查看目录 本来两个是想分开写的，但是我这只鸽子省选前两天才写完春测游记，就合并到一起了（ 春测 day 0 早上上完第二节课就出发了，很爽。 然后 huge 问我们初二的谁是班长，没人是。 然后 huge 让出来一个队长点点名啥的，然后大家 ......

题目分析： 考虑这是一个树形图，所以就先直接当作树来做。 这个题其实就是让我们求解有多少种拓扑序而且题目中边方向的限制其实就是在限制拓扑序的前后，而一般这种题在设计 $dp$ 状态时都会考虑将拓扑序放到状态里，因为如果不这样干拓扑序就很难限制。 也就是设 $dp[i][j]$ 表示以 $i$ 为根的 ......

给定一张 n×m 的网格地图:其中 * 代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。 x 代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。# 代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。 例如：给出 1×41×4 的网格地图 *xx*，这个地图上最多只能放置一个炸弹。给出另一 ......