带修莫队-笔记 /「Luogu P1903」数颜色-题解

通过Luogu P1903 数颜色/维护序列这道题目来学习一下 带修莫队
顾名思义,带修莫队 不仅要支持普通莫队的查询操作,还要支持数据中途的修改

比如这道题目,需要实现以下目标

  1. 查询$[L,R]$区间内不同颜色画笔的种数
  2. 将$pos$处的画笔替换为$color$颜色

达到这个目标,可以在普通莫队的基础上加一个时间维度,实现 带修莫队

阅读全文

浅析莫队算法的时间复杂度

这篇文章来记录一下莫队算法时间复杂度的简单(不严谨)计算

首先分析一下莫队算法的时间复杂度有哪些方面构成

  1. 对询问Query数组的排序
  2. 区间左指针的移动
  3. 区间右指针的移动
阅读全文

「网络流24题」总结及图示

问题编号 问题名称 问题模型 转化模型
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 骑士共存问题 二分图最大独立集 网络最小割
阅读全文

「CSP-S 2019」题解

~~今年的题真是毒瘤~~,一个蒟蒻要来写题解了

校门外有两棵树,一棵叫括号树一棵叫树上的数,这两棵树要被一匹叫格雷的马划分开为Emiya做饭,这两棵树问:那你猜猜我们的重心在哪啊

阅读全文

「CSP-S 2019」自闭游记

这次大概是第二年参加信息竞赛了(虽然去年什么也不会就摸了110分,省四)
按照惯例,该写篇游记(流水账)了

阅读全文

「图论算法」树上并查集 dsu on tree

$dsu\ on\ tree$($disjoint\ set\ union\ \text{on tree}$)算法,也称 __树上并查集__。使用了并查集的按秩合并(启发式合并)的方法,结合 树链剖分 中的 轻重儿子划分 ,对 树上暴力统计 进行了优化。使用这个算法需要满足以下两个条件:

阅读全文