MiQiu

两个前置状态共同完成一次松弛 问题 P1875 佳佳的魔法药水 编号 000 到 n−1n-1n−1 的每种药水都可以直接购买，也可以按照若干配方把一份 AAA 与一份 BBB 合成为一份 CCC。初始没有任何药水，需要求得到

缩点后给桥树的叶子配对 问题 P2860 [USACO06JAN] Redundant Paths G 牧场由一张连通无向图连接，允许继续修建连接任意两个不同牧场的新道路。要求添加尽量少的边，使任意两个牧场之间都能找到至少两条

在线维护树上路径经过次数 问题 P3038 [USACO11DEC] Grass Planting G 给定一棵初始边权全为零的树。操作 P u v 会把 uuu 到 vvv 简单路径上的每条边加一，操作 Q u v 查询相邻

圆方树上统计路径能够经过的原点 问题 P4630 [APIO2018] 铁人两项 在一张简单无向图中选择两两不同的起点 sss、切换点 ccc 和终点 fff。若存在一条从 sss 出发、经过 ccc 到达 fff 且不重复经

DAG 传递约简中的两个拓扑顺序 问题 P6134 [JSOI2015] 最小表示 给定一张没有重边的 DAG。可以删除一部分边，但删除后任意两点之间的可达关系必须与原图完全相同，求最多能够删除多少条边，也就是统计有多少条直接

已知全源最短路后枚举一条新增边 问题 P6464 [传智杯 #2 决赛] 传送门 给定一张连通无向正权图，可以选择两个教学楼建立一对传送门，使它们之间的距离变为零。需要选择最优端点，使加入传送门后所有无序点对最短路之和最小，每

有方向的路径最大差与树链拼接 问题 P3976 [TJOI2015] 旅游 一棵树上的每座城市有当前宝石价格。每次从 aaa 沿唯一简单路径走到 bbb，只能先买入一次再在之后经过的城市卖出，要求输出不亏损时的最大利润；完成询

先定位最小横坐标，再在列内定位纵坐标 问题 CF19D Points 维护一个动态点集，支持加入和删除坐标不超过 10910^9109 的点。每次询问 (x,y)(x,y)(x,y) 时，要在所有满足 x′>xx'>

浅谈线段树信息合并 基础线段树告诉我们，每个节点保存对应区间的摘要 Info，父节点再由左右儿子的摘要合并得到。 不过在真实问题中，难点在于到底留下什么信息，以及信息之间是如何合并的。在这个角度下，线段树的 merge 其实跟 二分答案的 check 很像。 对于区间和、最大值这类简单问题，答案本身就足够成为摘要。但当父区间中可能产生子区间内部没有出现过的新答案时，只保存当前答案就不再充分。 本文

线段树基础理论 线段树解决的是动态区间维护问题。它把一个区间递归划分成若干节点，每个节点保存对应区间的摘要，再通过合并这些摘要回答询问。 本文只讨论最基础的下标线段树：坐标范围预先确定，支持单点修改与任意区间查询。区间修改、懒标记、权值线段树和其他扩展在基础结构成立后再分别讨论。 一、问题原型 动态区间和