xixike

# Day -1 今天有 tbl 学长的课，害怕.jpg 上午不出意外的被 D 了 QwQ 可能是因为在二南的时候听过了一次 tbl 学长的课，所以这次听的时候有了点心理准备，受到的折磨没有想象中的那么大。 晚上大家一起在机房打了一场 ABC，结果集体降智，一个小时硬是没切掉 F，自闭了。 好不容易挺过了今天，晚上回家调了调网络流洗了个澡就睡了。 # Day 0 上午简单收了收东西，由于不用带被子被褥什么的，所以也没有什么需要带的。 吃午饭的时候看了男子冰球决赛，俄罗斯奥委会对战芬兰，看的时候已经 1​ : 1​ 了，本来还等着看无限加时赛呢，结果芬兰第三节不到 1...

# A. Hide and Seek 看了好久没看懂题...

不打算写太多的讲解了（其实是我也说不清楚 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 ，对于每个操作所在的区间，往线段树上对应的节点的...