1. 图上异或题
从雷暴那里看到的估计是 nfls 模拟赛题。
给定一张带边权图，询问从 1 开始出发的路径，边权异或和一共有多少不同的权值。还有若干次删边操作（永久的），删一次问一次。
P4151 【[WC2011]最大XOR和路径】的结论，取出任意生成树 \(T\)，假设所有从 \(1\) 出发又回到 \(1\) 的路径权值构成的集合为 \(A\)，在 \(T\) 中 \(1\) 到 \(u\) 的路径异或和是 \(f(u)\)，那么所有从 \(1\) 出发到 \(u\) 的路径权值集合就是 \(\{f(u)\oplus w\mid w\in A\}\)．
如果 \(x\) 能够通过若干 \(A\) 中的元素异或得到 \(y\)，那么就称它们之间等价。假设 \(A\) 线性基大小为 \(k\)，那么答案就是等价类个数 \(\times 2^k\)．
这个是因为等价具有传递性，等价类划分可以直接按照 \(x\) 与 \(A\) 中元素异或得到的最小值来划分。因为不同的 \(x\) 与 \(A\) 张成的线性空间要不然无交要不然完全相同。
删边就不是很难了，倒过来看成加边，对于每个极小简单环（这里是指最终挑选出的 dfs 树上由一条返祖边和它跨过的树边构成的环，因为仅有这些环就能表示出所有的环）都能求出它在哪个时刻开始形成，在哪个时刻开始和 1 连通，两者取 max 在那个时刻加入线性基即可。
每次线性基加入元素的时候，如果加入成功则直接重构一下所有 \(f\) 对应的等价类，加入失败那就只算新加进来的。
[ABC304Ex] Constrained Topological Sort
对于边 \(x\to y\)，\(\text{cmax}(l_y,l_x+1),\text{cmin}(r_x,r_y-1)\) 之后不管图，直接从前往后拿个堆贪心每次选扫过 \(l\) 的 \(r\) 最小的。首先转化前后限制等价，其次一定有 \(l_x<l_y\) 和 \(r_x<r_y\)，这样 \(x\) 在 \(y\) 前面加入，并且优于 \(y\) 弹出，自然有 \(p_x<p_y\) 的限制满足。
如果只 fix \(\text{cmin}(r_x,r_y-1)\) 也是对的。若存在解 \(P\)，先重标号使得拓扑序为 \(i\) 的是节点 \(i\)．在分配标号 \(x\) 时定义一个节点 \(y\) “可分配”当且仅当 \(L_y\leq x\) 且连向它的点均已分配完了标号。
若分配 \(x\) 时可分配的节点中 \(R\) 最小的是 \(y\)，那么调整说明将 \(x\) 分配给节点 \(y\) 依然是一个合法的解。
现在将 \(P=1,2,\cdots, n\) 调整为 \(P'=1,2,\cdots x-1,x+1,x+2,\cdots y,x,y+1,\cdots ,N\)．
- 首先 \([x+1,y-1]\) 中没有连向 \(y\) 的边（\(y\) 是可分配的，而这中间的点均未分配标号），所以 \(u\to v\) 则 \(P_u<P_v\) 的限制依然满足。
- \(L_i\leq P'_i\)：限制变紧的只有 \(y\)，而 \(P'_y=x\geq L_y\)．
- \(P'_i\leq R_i\)：
- 仅需说明 \([x+1,y-1]\) 中的满足即可。若其中的 \(z\) 是可分配的，那么 \(R_y\leq R_z\)；
- 若其中 \(z\) 是不可分配的，说明有一个可分配的点 \(w\) 能够走若干条边到达 \(z\)，那么 \(R_y\leq R_w<R_z\)．
- 说明了 \(R_y\leq R_z\)，那么有 \(P'_z=z+1\leq y\leq R_y\leq R_z\)．
2. 维护点和区间的完美匹配问题
利用 Hall 定理，区间的任意一个集合，其大小要 \(\leq\) 区间并起来之后的点数。如果有不合法，那么并起来之后若干连续的段一定有一个段是不合法的。去考虑点数，那就是不能有 \([L,R]\) 满足被包含在 \([L,R]\) 内的区间个数 \(>R-L+1\)．
3. 一类堆贪心前 k 优方案题
4. hdu 多校 R10 1002 Assignment
操作两两不交或包含。dp 出 \(f_{i,j,k}\) 表示从空开始覆盖区间 \([i,j]\)，有 \(k\) 个位置和 \(b_{[i,j]}\) 不一样的最小代价，然后容易用另一个 dp 统计出答案。那么转移就两种，一种是不存在 \([i,j]\) 这个操作，那么一定中间有个划分点 \(l\)，让 \([i,l]\) 和 \([l+1,j]\) 拼出来得到 \([i,j]\)；另一种存在 \([i,j]\) 操作。
没想到的就是这部分可以另设 \(g_{i,j,k}\) 表示从全是 \(b_i\) 开始覆盖 \([i,j]\) 的最小代价，也就是从 \(f\) 的定义修改了如果颜色是 \(b_i\) 那么可以忽略代价。这样 \(g_{i,l}\) 和 \(f_{l+1,j}\) 能拼出 \(g_{i,j}\)，这样就能用 \(g_{i,j}+A_{b[i],len}\) 来更新 \(f_{i,j}\)．
5. CF487E
建出圆方树，即为询问两点直接所有点双的点权 \(\min\)．因为对于点双中任意三个不同的点 \(x,y,z\)，一定存在一条 \(x\to y\to z\) 的路径。那就树剖维护圆方树，方点的权值定义为周围圆点的 \(\min\)。但是同一个圆点可能对应了很多个方点，于是对方点进行儿子批量维护父亲单独处理的套路，方点只记为所有圆点儿子的 \(\min\)，只需要在 LCA 是方点时看一下其圆点父亲的值即可。
6. CF666E
询问 \(s[l,r]\) 在 \(t\) 中出现次数，就对 \(s\) 和 \(t\) 作广义 SAM 然后把 \(t\) 放在上面跑，跑到的位置 cnt++，然后 \(s[l,r]\) 对应等价类的 parent 子树和即为答案。每个 \(t\) 看作一种颜色，就是子树颜色个数最大值及其位置，在 parent 树上线段树合并即可，定位 \(s[pl,pr]\) 对应的节点就倍增。
7. CF914F
没救了能被蓝题干爆的？？看到字符串匹配问题枚举字符串算法，但也要记得还有 fft 和 bitset 这两个东西。上 bitset，对每个字符开一个 bitset 表示它所在位置，询问的时候就位移一下 bitset，与一下，然后统计一下区间 1 的个数就行，复杂度是 \(\mathcal{O}(n^2/w)\)．
看这个问题太难了那就想根号，长度 \(>\sqrt n\) 的直接 kmp 跑出来答案。\(<\sqrt n\) 的就考虑分块，整块块内的查询就对每个块作一个后缀自动机，parent 子树和，\(\mathcal{O}(|y|)\) 定位等价类；散块块内用 hash 一个一个 check；块间一定是前面后缀拼上后面前缀，也是用 hash 一个一个 check。修改的时候重构所在块的 SAM 和 hash，这样复杂度就是 \(\mathcal{O}(n\sqrt n)\)．
8. CF603E
先想想怎么 check，思路历程大概是先想到是不是等价于匹配，发现四个点的菊花那样也是合法的，沿着匹配的思路走发现如果 \(u\to v\) 存在一条路径，那么将路径上的边的选取状态取反，即可使得 \(u,v\) 的度数奇偶性均取反。所以合法当且仅当每个连通块大小都是偶数，而且能选就选是最优的。
题解里的证明思路是考虑拉出来一棵生成树，然后直接对着生成树递归构造，如果这棵子树的根不满足度数条件就和父亲连。只需说明根也是偶数度数即可。
现在会 check 了，整体二分，solve(l,r,L,R) 表示处理 \([l,r]\) 的这些边的时候，已知答案范围是 \([L,R]\)，并且此时 \([1,l)\) 中 \(<L\) 的已经加入到并查集中，求出 \(mid=\frac{l+r}{2}\) 的答案 \(k\) 之后，递归到 solve(l,mid-1,k,R) 和 solve(mid+1,r,L,k)，向右递归的时候扫 \([l,mid]\) 里面权值 \(<L\) 的边加进去，回溯回来的时候撤销掉；向左递归的时候扫权值在 \([L,k)\) 中位置 \(<l\) 的边加进去，回溯回来的时候撤销掉。注意这里权值可能需要离散化一下，相同的也钦定一个顺序，这样在向左递归之前扫描桶的时候，单独分析分治每一层中的各个节点，它们的 \([L,R]\) 并起来得到了 \([1,m]\)，所以这里扫桶在同一层是 \(\mathcal{O}(m)\) 的，那么现在复杂度就是 \(\mathcal{O}(m\log m\log n)\) 的了。
9. CF576E
每种颜色搞个扩展域并查集，那么就需要加边删边查询连通性，LCT。。。线段树分治递归到叶子 \(i\) 的时候得到它是否修改成功，再在 \((i,nxt_i)\) 这个区间 push 上这个修改就行。咋都这么若至。。。
10. CF1037H
从大到到小枚举 \(T\) 的一个前缀 \(T[1,i]\)，判断 \(S[l,r]\) 中是否有一个子串是 \(T[1,i]\) 后面接一个比 \(T_{i+1}\) 更大的字符．
SAM：对 \(S\) 作 SAM，定位到 \(T[1,i]\) 对应节点，然后查询 \(>T_{i+1}\) 的后继节点，是否存在一个 endpos 在 \([l+i,r]\) 内。1. 线段树合并解决。2. 问题形式化成每次查询 SAM 一个节点是否有 \([l,r]\) 内的 endpos，离线下来枚举 \(r\)，把 endpos 为 \(r\) 的那个节点打一个 \(r\) 的标记，询问一个节点就是它 parent 子树中标记的最大值是否 \(\geq l\)，这样线段树即可解决。
SA：S 以及各询问串之间用比 \(a\) 小的字符连接起来．枚举 \(T\) 的一个前缀 \(T[1,len]\)，二分出 LCP 恰好为 len 且后一个字符比 \(T[len+1]\) 大的区间 \([L,R]\)，那么就是问 \([L,R]\) 中是否有后缀的编号 \(sa_i\) 是 \([l,r-len]\)，并且 \(i\) 要尽可能小。
11. CF1628E
颜色段均摊之后问题就是询问 \(x\) 到 \([l,r]\) 中的最短路径中最大边权是多少，先联想到二分答案，如果 \(\leq mid\) 的边连起来之后 \(x\) 和 \([l,r]\) 是连通的，那么答案 \(\leq mid\)．发现问题是《只经过 \(\leq x\) 的边》是否能将 \([l,r]\) 与 \(x\) 连通，从而想到 Kruscal 重构树。那么建出 Kruscal 重构树之后 \(x\) 与 \([l,r]\) 构成的虚树的根的权值即为答案。线段树维护区间 LCA 即可 一个点集的 LCA 是 dfn 最小/最大这两点的 LCA，于是只需要支持查询区间 dfn 极值即可。其实也不用再拿个 set 颜色段均摊，用线段树维护白点的 dfn 最小最大就行，好写一点。
12. CF1063F
呃之前口胡过但是又想了一遍才发现细节上有点偏差。题解。
13. CF1017G
先考虑没有 2 操作，发现就是询问 \(x\) 到根的路径的是否存在一个前缀满足修改次数 \(\geq\) 点数。移项之后就是初始每个点是 \(-1\)，然后操作 1 就是单点 +1，询问是否有个前缀和 \(\geq 0\)．有了操作 2 之后我们需要适当的修改点权。洛谷题解里有个比喻很好，这个看成一个晕染操作，假设 \(x\) 这个地方最大前缀和是 \(s\)，那么在 \(s\) 这个位置减去 \((s+1)\)，用这个来吸收墨量，然后将子树其他点点权均改成 -1 就行。
如果 \(f(i)\) 是积性函数，想要求解 \(\sum_{i=1}^nf(ix)\) 的值。之前遇到过这个问题，是 \(f=\varphi\) 且 \(\mu^2(x)=1\) 的情况，现在来看一下通解应该怎么处理，先看看 \(\mu\) 咋做。
假设 \(\mu^2(x)=1\)，\(\mu(ix)\) 并不是积性函数，但我们想处理积性函数，于是当 \(i\bot j\) 时观察 \(\mu(ix)\mu(jx)\) 和 \(\mu(ijx)\)：\(i,j\) 其中一个与 \(x\) 不互质那么两侧都是 \(0\)；否则 \(i,j,x\) 两两互质，那么左侧是 \(\mu(i)\mu(j)\mu(x)\mu(x)\)，右侧是 \(\mu(i)\mu(j)\mu(x)\)，于是令 \(g(i)=\mu(ix)/\mu(x)\)，那么 \(g(i)\) 就是一个积性函数了。
然后去考察 \(g\) 的贝尔级数，若 \(p\nmid x\)，那么 \(g_p(z)=1-z\)，若 \(p\mid x\) 那么 \(g_p(z)=1\)．
凑杜教筛，另设积性函数 \(h\)，若 \(p\nmid x\)，那么 \(h_p(z)=\frac{1}{1-z}\)，若 \(p\mid x\) 那么 \(h_p(z)=1\)，此时 \(h(i)=[\gcd(i,x)=1]\)，称其为 \(\mathbf{1}_x\)．
所以现在有 \(g*\mathbf{1}_x=\epsilon\)，如果能够求 \(\mathbf{1}_x\) 在所有 \(\left\lfloor\frac{n}{i}\right\rfloor\) 位置处的前缀和就可以杜教筛 \(g\) 了，\(\sum_{i=1}^n\mathbf{1}_x(i)=\sum_{d|x}\left\lfloor\frac{n}{d}\right\rfloor\)，整除分块的时候要求 \([l,r]\) 内有多少 \(x\) 的因子，注意到所有 \(r\) 都是 \(n\) 的基本和组，那么将这 \(\mathcal{O}(\sqrt n)\) 个 \(\left\lfloor\frac{n}{i}\right\rfloor\) 和 \(x\) 的所有质因子排序预处理前驱后继，这样就能在 \(\mathcal{O}(\sqrt n)\) 的时间复杂度计算 \(\mathbf{1}_x\) 的前缀和了。它同样可以线筛，那么现在就做到了 \(\mathcal{O}(n^{2/3})\) 的复杂度。
同样来尝试 \(\varphi\)，即使 \(\varphi(ix)\) 并不是关于 \(i\) 的积性函数，但我们仍然去考虑它在质数次幂的取值形成的 ogf，若 \(p\nmid x\) 那么 \(f_p(z)=\frac{1-z}{1-px}\)，否则假设最大的正整数 \(k\) 使得 \(p^k\mid x\)，那么有 \(f_p(z)=\frac{(p-1)p^{k-1}}{1-px}\)，若设 \(g(i)=f(i)/\varphi(x)\)，那么 \(p\mid x\) 时 \(g_p(z)\) 就变为了 \(\frac{1}{1-px}\)，这里需要证一下 \(g\) 是个积性函数：
若 \(f(i)\) 是关于 \(i\) 的积性函数，若 \(f(x)\neq 0\) 那么 \(f(ix)/f(x)\) 是关于 \(i\) 的积性函数。直接按定义 \(\frac{f(ix)}{f(x)}\times \frac{f(jx)}{f(x)}=\frac{f(ijx)}{f(x)}\) 即 \(f(ix)f(jx)=f(ijx)f(x)\)，此时考察一个质因子 \(p\)，假设它在 \(i,j,x\) 中的次幂分别是 \(e_i,e_j,e_x\)，首先 \(e_i,e_j\) 至少有一个为 0，假设 \(e_i=0\)，那么它对左侧的贡献是乘上 \(f(p^{e_x})f(p^{e_j+e_x})\)，对右侧的贡献是 \(f(p^{e_j+e_x})f(p^{e_x})\)，所以等式左右相等。
于是同样有 \(h(i)=[\gcd(i,x)]=1]\)，那么 \(g*h=id\)，可以杜教筛。
这里的重点在于，\(f'(x)=f(ix)/f(x)\) 是积性的，如果想求 \(f(ix)\) 的前缀和，就可以转化为求 \(f'(x)\) 这个积性函数的前缀和问题。如果 \(f(x)=0\) 那么 \(x\) 存在质数次幂 \(p^k\) 满足 \(f(p^k)=0\)，于是有 \(p\nmid i\) 时 \(f(ix)=0\)，所以可以 \(n\leq \left\lfloor\frac{n}{p}\right\rfloor,x\gets px\)．
杜爷是怎么想到这个东西呢？考虑 \(f(ix)\) 实际上对 \(x\) 的质因子的贝尔级数的系数进行了一个位移，不是积性的原因是常数项不为 1，那么除掉常数项就得到了这个构造。
标签：杜爷,那么,frac,ix,积性,mu,leq From： https://www.cnblogs.com/do-while-true/p/duyesieve.html