xixike

不打算写太多的讲解了（其实是我也说不清楚 QwQ），这里只贴一份代码留着以后抄。 # 后缀数组（SA） 洛谷 P3809 【模板】后缀排序 #include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;char s[N];int sa[N], rk[N], hei[N], x[N], y[N], cnt[N];int n, m = 127, tmp[N];inline void update(int Rk[], int tp[]){ for(int i = 1; i <=...

emm……NTT 左转去看各位神犇的博客吧 QwQ 这里只贴代码及部分操作的推导过程。 # 首先是喜闻乐见的 NTT 多项式乘法板子 （这个就不解释了） marknamespace NTT{ ll lim, len; inline ll qpow(ll a, ll b){ ll res = 1; while(b){ if(b & 1) res = res * a % mod; a = a * a % mod, b >>= 1; } return res; } inline...

常见的数论函数 恒等函数： I(n)=1I(n) = 1I(n)=1 元函数： ϵ(n)=[n=1]\epsilon(n) = [n = 1]ϵ(n)=[n=1] 单位函数： id(n)=nid(n) = nid(n)=n 除数函数：输出函数用 σk(n)\sigma_k(n)σk​(n) 表示 nnn 的 kkk 次方的的和，即 σk(n)=∑d∣ndk\sigma_k(n) = \sum\limits_{d | n} d^kσk​(n)=d∣n∑​dk。 约数个数函数，即 σ0(n)\sigma_0(n)σ0​(n)，通常用 d(n)d(n)d(n) 表示：...

# 主要思想 WQS 二分也叫带权二分，主要解决一类凸包上的问题。 假设当前你有一个很难计算的凸函数 f(x)f(x)f(x)，此时你要计算一个指定的 f(n)f(n)f(n)，如何快速求出呢？ 我们可以去二分一个斜率 kkk，然后计算斜率为 kkk 的一条直线落到这个凸壳上时的交点。 设这个交点为 (x,f(x))(x, f(x))(x,f(x))，再设函数 g(k)g(k)g(k) 表示表示斜率为 kkk 的直线落到凸壳上时的截距。 那么： f(x)=g(k)+kxg(k)=f(x)−kxf(x) = g(k) + kx\\ g(k) = f(x) -...

不打算详细写了，强推一波 yyb 神仙的博客 Splay 入门解析【保证让你看不懂（滑稽）】 （这篇博客的代码完全是按照 yyb 的博客写的，并有一些补充，包括 pushup 及查询第 k 大的整数等等） 这里列几个注意事项吧： SplaySplaySplay 过程中，如果 x,yx, yx,y 为同一种儿子，那么先旋转 yyy，再转 xxx，否则旋转两次 xxx。 rotate 时的顺序： 先改 zzz 的儿子（zzz 的儿子从 yyy 变成 xxx） xxx 的儿子中变动的那个儿子（从 xxx 的儿子变成 yyy 的儿子，至于是哪个建议背过，背不过的话现推一下规律） 最后令 yyy...

# 前言 说是学习笔记，其实窝并没有打算写太多（太麻烦了，而且我的理解还不是特别深，可能也写不清楚），所以打算大概写两句，然后贴个板子。 # 前置知识 Miller−RabinMiller-RabinMiller−Rabin 素性测试。 倍增基础应用。 # Miller−RabinMiller-RabinMiller−Rabin 素性测试 我们知道有费马小定理： ap−1≡1(modp)a^{p - 1} \equiv 1\pmod pap−1≡1(modp)，ppp 是质数且 aaa 是小于 ppp...

虽然很久之前学过一遍，但是又忘了 QwQ，于是重新复习了一遍。 CDQ 分治是一个离线算法，也只能用于离线问题的处理上。 # 主要思想 把当前区间分成两半，向下递归处理。 左边和右边独立的贡献计算出来之后，再计算左边对右边的贡献。 通常会套上一些树状数组之类的数据结构（不然和暴力有啥区别 QwQ） # 例题 板子题：P3810 【模板】三维偏序（陌上花开） # Solution 先按第一维从小到大排序，对于区间 (l,r)(l, r)(l,r)，递归处理 (l,mid)(l, mid)(l,mid) 和 (mid+1,r)(mid + 1, r)(mid+1,r)。 由于已经按照 aaa...

# 问题引入 给一些操作，只在 l∼rl \sim rl∼r 时间段内有效。 给一些询问，查询在某一时间内所有操作的贡献。 # 主要思想 我们可以把操作和询问都离线下来，然后对于时间轴建一棵线段树。 对于操作，相当于是在线段树上进行区间修改；对于查询，不停地向下递归，统计答案，回溯时撤销掉操作。 这样的思想被称之为线段树分治。 # 例题 P5787 二分图 /【模板】线段树分治 # Solution 出现二分图的条件是不存在奇环，可以使用扩展域并查集维护。 再来看如何建树，我们先按照时间轴分区间，然后对于每个点开一个 vector ，对于每个操作所在的区间，往线段树上对应的节点的...

主席树的最基础的操作就是查询历史版本区间第 kkk 大，带修。 这个问题的基础解决思路：对于每次修改都建一棵权值线段树，显然空间开不下。 这时可持久化线段树的思路就应运而生了。 主要思想： 不难发现，每次修改只会有一条链上的值发生改变，所以我们不需要建出整棵新树，只需要把新建那条链上的点即可。 所以空间就是 nlog⁡nn\log nnlogn 的。 我们还要在权值线段树上做个前缀和来方便查询，每次查询时，就是在权值线段树上二分的过程。 注意到我们要建的是权值线段树，所以要对输入的值做一个离散化。 不多说了，直接贴代码吧。 code:code:code: mark#include...

# 点双，边双 （掌握较为熟练） # 点双： 定义：删去一个点之后，图仍然联通，则称这个图是点双联通的。一个无向图里最大的点双联通子图称为点双连通分量。 算法：跑 Tarjan，回溯过程中若 lowy≥dfnxlow_y \geq dfn_xlowy​≥dfnx​ 就出栈直到目标节点出栈，弹出的点为一个点双。 # 边双： 定义：类似于点双，只不过条件都改为边。 算法：同样和点双很像，如果有 lowy>dfnxlow_y > dfn_xlowy​>dfnx​ 那么存在点双，弹栈加点即可。 # kmp & AC...