「杂谈」我与几门编程语言之间的故事
第二次学完 Rust 基础之后没事闲的来写篇博客讲讲故事
本来想只写 Rust 来着，想了想又觉得其它语言不说也不好，干脆都写下来吧（
阅读全文
通过SPOJ 10707 COT2-Count on a tree II这道题目来学习一下 树上莫队
当需要离线查询 树上 的多区间问题时,可以使用 树上莫队 来解决
主要通过 欧拉序 将树转化为一条链,然后在链上执行普通莫队的操作
第二次学完 Rust 基础之后没事闲的来写篇博客讲讲故事
本来想只写 Rust 来着，想了想又觉得其它语言不说也不好，干脆都写下来吧（
通过SPOJ 10707 COT2-Count on a tree II这道题目来学习一下 树上莫队
当需要离线查询 树上 的多区间问题时,可以使用 树上莫队 来解决
主要通过 欧拉序 将树转化为一条链,然后在链上执行普通莫队的操作
通过AtCoder 1219 歴史の研究这道题目来学习一下 回滚莫队
回滚莫队 适用于容易进行add操作,而不容易实现del的情况
通过莫队的分块,指针移动的思想,可以让左指针进行回滚操作, 近似 达到del的效果
通过Luogu P1903 数颜色/维护序列这道题目来学习一下 带修莫队
顾名思义,带修莫队 不仅要支持普通莫队的查询操作,还要支持数据中途的修改
比如这道题目,需要实现以下目标
达到这个目标,可以在普通莫队的基础上加一个时间维度,实现 带修莫队
这篇文章来记录一下莫队算法时间复杂度的简单(不严谨)计算
首先分析一下莫队算法的时间复杂度有哪些方面构成
Query数组的排序| 问题编号 | 问题名称 | 问题模型 | 转化模型 |
|---|---|---|---|
| 1 | 飞行员配对方案问题 | 二分图最大匹配 | 网络最大流 |
| 2 | 太空飞行计划问题 | 最大权闭合图 | 网络最小割 |
| 3 | 最小路径覆盖问题 | 有向无环图最小路径覆盖 | 网络最大流 |
| 4 | 魔术球问题 | 有向无环图最小路径覆盖 | 网络最大流 |
| 5 | 圆桌问题 | 二分图多重匹配 | 网络最大流 |
| 6 | 最长不下降子序列问题 | 最多不相交路径 | 网络最大流 |
| 7 | 试题库问题 | 二分图多重匹配 | 网络最大流 |
| 8 | 机器人路径规划问题 | $IDA*$ | $IDA*$ |
| 9 | 方格取数问题 | 二分图点权最大独立集 | 网络最小割 |
| 10 | 餐巾计划问题 | 线性规划网络优化 | 最小费用最大流 |
| 11 | 航空路线问题 | 最长不相交路径 | 最小费用最大流 |
| 12 | 软件补丁问题 | 最小转移代价 | 最短路径 |
| 13 | 星际转移问题 | 网络判定 | 网络最大流 |
| 14 | 孤岛营救问题 | 分层图最短路径 | 最短路径 |
| 15 | 汽车加油行驶问题 | 分层图最短路径 | 最短路径 |
| 16 | 数字梯形问题 | 最大权不相交路径 | 最小费用最大流 |
| 17 | 运输问题 | 网络费用流量 | 最小费用最大流 |
| 18 | 分配问题 | 二分图最佳匹配 | 最小费用最大流 |
| 19 | 负载平衡问题 | 最小代价供求 | 最小费用最大流 |
| 20 | 深海机器人问题 | 线性规划网络优化 | 最小费用最大流 |
| 21 | 最长k可重区间集问题 | 最大权不相交路径 | 最小费用最大流 |
| 22 | 最长k可重线段集问题 | 最大权不相交路径 | 最小费用最大流 |
| 23 | 火星探险问题 | 线性规划网络优化 | 最小费用最大流 |
| 24 | 骑士共存问题 | 二分图最大独立集 | 网络最小割 |
题目传送门: 「Luogu P1494」小Z的袜子
一道推公式，后使用莫队 玄学 优化的题目
~~今年的题真是毒瘤~~,一个蒟蒻要来写题解了
校门外有两棵树,一棵叫括号树一棵叫树上的数,这两棵树要被一匹叫格雷的马划分开为Emiya做饭,这两棵树问:那你猜猜我们的重心在哪啊
这次大概是第二年参加信息竞赛了(虽然去年什么也不会就摸了110分,省四)
按照惯例,该写篇游记(流水账)了
$dsu\ on\ tree$($disjoint\ set\ union\ \text{on tree}$)算法，也称 __树上并查集__。使用了并查集的按秩合并(启发式合并)的方法，结合 树链剖分 中的 轻重儿子划分 ，对 树上暴力统计 进行了优化。使用这个算法需要满足以下两个条件：