7.1k 字 10 分钟

# 树链剖分（重链剖分） 模板：洛谷 P3384 【模板】轻重链剖分/树链剖分 写在前面：强烈建议初学的同学如果不理解的话先手写一遍（像我一样），非常有助于理解 # 概念： 重儿子： 一个节点所有儿子中最大的儿子 轻儿子： 一个节点除重儿子之外的其他儿子 特别地，叶子节点既没有重儿子也没有轻儿子 重链： 重儿子连接形成的链叫重链 # 主要思想： 把一颗树拆成许多条链，把树上操作改为链上操作（区间操作），并利用线段树或树状数组等数据结构维护，以降低时间复杂度 每次进行操作时，先修改重链，再修改轻链 # 常见操作： 将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上...
3.7k 字 5 分钟

洛谷 P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 # 主要思想： 顾名思义，线段是合并就是将多棵线段树合并到一起，要求线段树维护的数据可以支持合并，例如最大值，区间和等。 我们在进行合并时要把两棵线段树上相同的结构点合并到一起，换句话说，就是两棵线段树当前要合并的点所表示的区间是一样的。 例如，区间长度是 888，那么我们合并时要把 [1,8][1,8][1,8] 和 [1,8][1,8][1,8] 合并到一起 [5,8][5,8][5,8] 和 [5,8][5,8][5,8] 合并到一起。 好了，我们知道了主要思想后下面来看如何实现。 #...
5.3k 字 7 分钟

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

不打算写太多的讲解了（其实是我也说不清楚QwQ），这里只贴一份代码留着以后抄。 # 后缀数组（SA） 洛谷 P3809 【模板】后缀排序 1234567891011121314151617181920212223242526272829303132333435363738394041424344#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,...
13k 字 18 分钟

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

常见的数论函数 恒等函数： 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) 表示：...
3.7k 字 5 分钟

# 主要思想 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) -...
3.4k 字 5 分钟

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