memset0's blog

今天和自己喜欢的小姐姐聊了天呢，
小姐姐还给了我好多建议呢，
小姐姐还给我加油了呢，
小姐姐还抱抱我了呢。

那个小姐姐是个敲可爱滴男孩纸呢，
好希望能和他面姬啊，
那么 memset0 要加油了呢！

QAQ 写树套树的时候忽然用到。。。

最近忽然发现 BZOJ 的权限题还是很多的（可能是因为以前搜不到就不搜了现在上 DARKBZOJ ），看来还是得众筹买个权限号了（雾

这是一道傻逼数据结构题，由于数据范围小，各种奇葩算法随便过。本菜鸡就写了个普通的树状数组套莫队，各位大佬不要见笑。

题意：

给你个 $1000 \times 1000$ 的矩阵，每次交换任意两个不重合的子矩阵，求最后的结果

如果你是一位数据结构学傻的选手（像我），那么第一感觉肯定是用平衡树做，复杂度 $O(m \times n \log n)$ ，不过不幸的是，由于常数巨大，最后得分甚至可能不如暴力的 memcpy 。

如果你是一个不会高级数据结构的普及选手你说不定就能想到链表。维护一个矩形的链表，然后每次交换就分别把两块矩阵取出再拼接上去。

这道黑题为什么那么水 QAQ
这道题在 BZOJ 上为什么又又又又又是权限题

本题求区间众数，强制在线。

对于每次查询，必定可以分为整块的和非整块的，我们先预处理出第 $i$ 块到第 $j$ 块的众数（ $max[i][j]$ ）和某个数 $i$ 在前 $j$ 个块内的前缀和（ $sum[i][j]$ ）。对于非整块的部分 $O(\sqrt n)$ 暴力加到桶里，加上整块中的个数判断能否更新答案。然后判断 $l$ 与 $r$ 之间的块的众数是否能否更新答案。

预处理的话 $max$ 和 $sum$ 数组全都暴力扫一遍更新，时间复杂度 $O(n \sqrt n)$，详见代码。

时间复杂度：$O(n \sqrt n + m \sqrt m)$

为什么这题的名字这么奇怪？
为什么这题的题解都是分块？

好，我们讲怎么用线段树做：
首先先把 $1$ 和 $2$ 两个操作用线段树维护出来（这很简单），至于排序我们直接统计区间内每个字母的数量（用操作 $1$ ），然后再直接放回去即可（用操作 $2$ ）。

以及这题大小写字母都会出现，无视即可。

时间复杂度 $O(n \log n \times 26)$

逐行 DP ，一行一行扫下去，显然之前选择的是那几列不重要，重要的是有多少列已经放了一个棋子，多少列已经放了两个棋子。

用 $f[k][i][j]$ 表示到第 $k$ 行为止，有 $i$ 行放了一个棋子， $j$ 行放了两个棋子的方案数，没放棋子的行数可以由此推出。

给树分块即可，为树上分块 / 树上莫队做铺垫。

给定一个序列，要求兹滋： 区间加数、区间除以数、区间求和、区间求最小值。

其他都很简单，关键在于怎么解决区间除法。

一开始很容易想到之前的 “花神游历各国” ，但是这题并不能这样做（有区间加数），感觉线段树不可做想分块然而分块照样没法解决除法的问题。

正解则是将除法转换为减法，如果当前区间的最大值和最小值与除以除数的数的差值相同，那么把除数变成减数。

复杂度为 $O(n \log^2 n)$ 据称可以用势能分析，但是本蒟蒻太菜了不会，因此略过 QAQ。

在主席树的基础上做可持久化数组，在可持久化数组的基础上做可持久化并查集。

然而路径压缩的话数组的修改次数可能会很大，但是每次修改是 $O(\log n)$ 的，可能会炸。所以我们要用一种类似启发式合并的方法，把小的往大的合并，这样总的复杂度是 $O(n \log n)$ 的。

可以把并查集中的联通块看成一颗多叉树，合并时，把最深点的深度小的往大的合并，后者把树的大小小的往大的合并。笔者采用的是后者，其实原理基本是一样的。

真是纳闷，为什么这题在 BZOJ 上是权限题？？？

首先你需要了解一下 这种算法，然后你在重构树上树形 DP 处理出子树中距离的最小值，最后对于每次询问倍增找出最高点回答即可。

过程就不详细说啦，相信在坐的各位大佬早就会啦。。。

不过也有 sqq 这种巨佬写了可持久化并查集 AC 了的 QAQ ，下次写写。

洛谷 SPJ 坏了，一个月了没修好。怎么回事啊？

UPD: QQ 群里 @ 了一下 chen_zhe 竟然很快修好了

回到正题：本题是 2-SAT 裸题，做之前可以参考一下洛谷的模板题，下面假装你已经看过并 AC 了那道题。

对于 $a$ 、 $b$ 、 $c$ 三种地图，都是不允许一辆车，而允许另外两辆。对于 $x$ 地图，显然不能交给 2-SAT 算法解决，暴力枚举他是 $a$ 地图还是 $b$ 地图（如果 $a$ 和 $b$ 都不行那么 $c$ 也不行）。

关于连边，用 $u$ 表示第 $i$ 场游戏使用赛车 $h_i$ 所对应的点，$v$ 表示 第 $j$ 场游戏赛车 $h_j$ 所对应的点，$u’$ 和 $v’$ 则表示对应地图可以使用的另一辆赛车所对应的点。

如果 $h_i$ 不符合第 $i$ 张地图的限制条件，那么这种约束肯定不会遇到，跳过即可。

如果 $h_j$ 不符合第 $j$ 张地图的限制条件，那么说明 $i$ 的这种情况肯定不能取到，就从 $u$ 向 $u’$ 连一条边。

否则说明如果取了 $h_i$ 就一定要取 $h_j$ ，连接边 $u$ 到 $v$ 和 $u’$ 到 $v’$ 即可。

另外，由于 2-SAT 要跑很多遍，所以请注意清空数组（我不会告诉你我没有清空 dfn 拿到了 $90$ 分的好成绩）。

一道经典的搜索题。由于棋子没必要也不可能和非空格的棋子交换，目标棋子也只可能通过与空格交换位置达到目标位置，因此我们只需要存储空格和目标棋子的位置即可。这样爆搜即可拿到 $80$ 分。

接着考虑能否继续优化：每次目标棋子改变位置空格必须在他旁边，因此存储除了初始状态和终止状态外的空格不在目标棋子旁边的状态没有意义。因此我们可以用 BFS 处理出状态之间转移的代价，然后用 SPFA 等最短路算法跑一遍即可。本题由于状态个数和状态之间的边不多，正常常数的 SPFA 不会被卡掉。

需要注意的是：在使用 BFS 搜索空格转移代价时不能经过目标棋子。
算法时间复杂度：$O(n^4)$

又是一道非常水的黑题。给你一个双向图，你需要代替炎魔之王拉格纳罗斯（？？？）会净化图中的所有环，也就是除了链以外的强连通分量，成为一颗无根树。然后询问树上距离。

已知每个数最多能被开方而减小的次数是有限的，当当前的数是 $0$ 或 $1$ 时就没有必要操作。

所以我们可以用线段树维护区间最大值，如果当前的最大值已经等于 $0$ 或 $1$ ，就无需操作，否则逐个修改。

复杂度 $O(n \sqrt {10^9} \log n)$ ，可过。

区间取模操作同理。

理论上来说资瓷区间开方 / 取模和单点修改，算是优美的暴力吧。

多倍经验（数据范围和要求略有不同）：

1. BZOJ3211 - 花神游历各国
2. 洛谷4145 - 上帝造题的七分钟2 / 花神游历各国
3. SPOJ2713 - GSS4 - Can you answer these queries IV

大佬 abc2237512422 的洛谷美化脚本推荐：

使用方式：

1. 搜索安装 Stylus （或 Stylish ）的浏览器插件。

2. 打开 https://userstyles.org/styles/157651/material-luogu-material 并安装。

还可在上面的网页进行个性化设置打造自己最喜欢的洛谷样式 qwq.

我在学习点分治时，一直卡在这道题，今天我一鼓作气想尽办法终于把她 AC 了。

将要讲述的方法是动态点分治，有另一种链分治的方法个人感觉较为麻烦且不自然就不在此赘述。

首先静态点分治一遍建立点分树，并算出初始答案，存储每个节点作为重心时到上一个节点的边。当动态修改时从底层向上逐层修改直到抵达根节点。

对于每个节点，我们存储每个子树中距离最远的点（用 son 维护）和距离当前节点距离最远的点（用 hep 维护），最后再维护一个答案堆 ans 供查询。这个堆要资瓷添加和删除操作，可以用经典的建两个堆的方法，一个插入，一个删除即可。

其他当前子树中没有白色时应该返回 $-inf$ ，否则与当前子树的根节点是白色节点时等价的 qwq。

把淘汰赛问题转换为一棵生成树，每一条边相当于一个二选一淘汰的过程。

三维偏序，一维一维解决：第一维排序，第二维 CDQ ，第三维树状数组（或 CDQ ）。

先按照 $a$ 进行排序，考虑 CDQ ，先分治左右两边，使得左右两边的节点都按 $b$ 排序，于是依次从两边取（优先 $b$ ， $b$ 相等优先 $c$），左边的取出时在树状数组中更新，右边的取出时从树状数组中查询，考虑贡献。

需要注意的是，$a$ 、 $b$ 、 $c$ 的值都相同的节点有可能互相产生贡献，很难用 CDQ 解决，于是可以将这些点缩为一个，并单独计算他们内部互相产生的贡献。

巧妙的使用满流的特性解决问题。

对每一天，连一条容量为 $INF - 需求人数$ 的边，对于补充的人连一条容量为 $INF$ ，花费为价格的边。

对这个图跑最小费用最大流，其中最大流一定是 $INF$ ，最小费用即答案。