Daniel_yuan's Blog

在网上学习了 Hall 定理后决定写这么个东西。

如有雷同或涉及侵权，请联系博主。

这个题目的 \(2\) 操作代表着需要维护一个可持久化的东西。

但是因为它没有强制在线，根据常识，可以离线生成一个操作树来降低思考难度。

不难发现最终的字符串的长度可能会非常长，可以达到 \(n\cdot x=10^9\) 级别，这提示我们不能从字符串本身入手。

众所周知，只要把模建好，什么题都可以用网络流/费用流跑。

随着这些算法普及度的提高，出题人也就不再局限于单纯的网络流/费用流，而模拟费用流就是其中衍生出来的一个上限很高的算法。

由于博主水平有限，在此记录一些比较简单的模拟费用流问题和思路。

Day -INF

莫队算法是一个很妙的算法，它可以通过对查询离线分块来降低算法复杂度。

但是仔细分析你会发现，莫队所有的复杂度都是修改左右端点造成的，而查询是 \(O(1)\) 的。

也就是说我们可以在莫队中套一个修改 \(O(1)\)，查询 \(O(1\sim \sqrt{n})\) 的数据结构，这样总复杂度依旧是 \(O(n \sqrt{n})\) 的，但是它却可以做更多的事情。

设 \(F\) 是斐波那契数列，其定义是对于 \(x\leq 2\)，\(F(x)=1\)；对于 \(x\geq 3\)，\(F(x)=F(x-1)+F(x-2)\)。

1. 查找某个数 \(x\) 可以被给出基底 \(A\) 如何异或得到

把基底 \(A\) 做线性基，并且在线性基的同时维护线性基中每个元素是由基底中的哪些元素异或得到的，记作 \(S\)，那么在查询的时候，把对应位置的 \(S\) 也一起异或，就可以得到最终所求。

2. 把基底 \(A\) 的一个数 \(A_i\) 与另一个数 \(x\) 交换，保证交换后基底 \(A'\) 仍然满足基底的性质

同上，在线性基的同时维护线性基中每个元素是由 \(A\) 中的哪些元素异或得到的，记作 \(S\)。先查询 \(x\) 怎么被 \(A\) 表示，因为 \(A'\) 依旧满足基底的性质，那么如果用 \(A\) 来表示 \(x\)，那么 \(A_i\) 一定会被用到。所以 \(A_i\) 也可以用 \(A\) 中的数和 \(x\) 一起表示，那么就可以直接交换 \(x\) 和 \(A_i\)，然后去更新线性基中的每个位置的 \(S\) 即可。

被个三进制下位运算题搞自闭了，琢磨了好久才有了一个看似贼简单的做法，故记录一下。

Day -1

吉老师是我们的红太阳，紧随吉老师的步伐。