Extended Eratosthenes Sieve

扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ (这里以实际运行效果估计,实际复杂度据说和洲阁筛一样)求出一般积性函数的前缀和,消耗 $O(\sqrt{n})$ 的空间

矩阵树定理学习笔记

矩阵树定理的学习笔记和部分线性代数的知识,记录三道经典题目及变元矩阵树定理。

「黑科技」静态化 STL 容器内存

在 OI 中,我们手写的数据结构几乎都是静态内存的,而 STL 中的容器由于内存动态化的原因在做题中容易 TLE,这里介绍几种常见容器静态化内存的方法。

常数优化的技巧及应用

作为一个先学工程的蒟蒻 oier,也就只能在卡常上有一些技巧了……

然而我太弱,并没有去成 WC,虽然感觉 T2 卡三级缓存不是应该很好卡吗?

这里总结松爷的一些技巧和记录一些其他技巧及一些实际例子。

Link-Cut Tree学习笔记

在数据结构中有一类问题叫做动态树问题(DynamicTree),它会要求你对一颗树进行切割和拼接,然后再在上面维护传统的数据结构能维护的值,为了完成这一类问题,就有了很多相应的算法来解决这类问题,Link-Cut Tree 就是其中一种比较方便实用的算法。

后缀自动机应用总结

这里保存一些后缀自动机常见应用和例题,不断完善中,更多的还是看补档计划吧……

后缀自动机学习笔记

后缀自动机学习总结

前置技能

有限状态自动机

有限状态自动机 DFA,功能就是识别字符串,令一个自动机 $A$,若能识别字符串 $S$,就记为 $A(S) = true$,否则 $A(S) = false$。自动机由五个部分组成,$alpha$ 为字符集,$state$ 状态集合,$init$ 初始状态,$end$ 结束状态集合,$trans$ 状态转移函数。

$tarns(s, ch)$ 表示当前状态是 $s$,在读入后字符 $ch$ 后所到达的状态;同时 $tarns(s, str)$ 表示当前状态是 $s$,在读入后字符串 $str$ 后所到达的状态。

如果 $trans(s, ch)$ 这个转移不存在,我们设其为 null,同时 null 只能转移到 nullnull 表示不存在的状态。

上下界网络流学习总结

有上下界的网络流。
$(u, v)$ 为一条边,$s$ 为源,$t$ 为汇,$S$ 为超级源,$T$ 为超级汇,$d$ 记录下界和。

数论函数及积性函数总结

数论函数:定义域为正整数的函数。

积性函数

定义

积性函数:对于任意两个互质的正整数 $a,b$ ,均满足 $f(ab)=f(a)f(b)$ 的函数 $f$

完全积性函数:对于所有正整数 $a,b$ ,均满足 $f (ab) = f (a) f (b)$ 的函数 $f$

定义逐点加法: $(f + g)(x) = f(x) + g(x)$,$(f \cdot g)(x) = f(x)g(x)$

块状链表模板

在进行算法设计时,我们常用的两种线性数据结构是数组和链表。它们各有优缺点。数组特点是元素在内存中紧挨着存储,因而优点是定位快 $O(1)$,缺点是插入删除慢 $O(n)$;而链表则不同,它通过指针将不同位置的元素链接起来,因而优缺点与数组正好相反:定位慢 $O(n)$,插入删除快 $O(1)$。而块状链表,它将数组和链表的优点结合来,各种操作的时间复杂度均为 $O(\sqrt n)$。

非旋转式 Treap 学习笔记

树堆,在数据结构中也称 $Treap$,是指有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为 $O( \log n )$。

相对于 $AVL$ 和红黑树,其实现简单,相对于 $Splay$,其效率更高,相对于替罪羊和 $SBT$,其适用范围更广(尤其是非旋转式Treap)。

计算几何模板

不完全模板如下,长期更新中(已弃):

线段树模板

静态内存指针版动态开点线段树…(这名字有毒)

自行修改 $pushDown$ 和 $update$ 等…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct Node {
Node *lc, *rc;
int l, r;
long long val;
int tag;
inline void clear() { val = tag = 0; }
inline void cover(const int delta) { tag += delta, val += (long long)delta * (r - l + 1); }
inline void pushDown() { if (tag) lc->cover(tag), rc->cover(tag), tag = 0; }
inline void update(const int l, const int r, const int delta) {
if (l > this->r || r < this->l) return;
else if (l <= this->l && r >= this->r) cover(delta);
else pushDown(), lc->update(l, r, delta), rc->update(l, r, delta), val = lc->val + rc->val;
}
inline long long query(const int l, const int r) {
register long long ret = 0;
if (l > this->r || r < this->l) return 0;
else if (l <= this->l && r >= this->r) return val;
else return pushDown(), ret += lc->query(l, r), ret += rc->query(l, r), ret;
}
} pool[(MAXN + 10) << 4], *root, *tail = pool;
inline void build(Node *&rt, const int l, const int r, int *a) {
rt = tail++, rt->clear(), rt->l = l, rt->r = r;
if (l == r) { rt->val = a[l]; return; }
register int mid = l + r >> 1;
build(rt->lc, l, mid, a), build(rt->rc, mid + 1, r, a);
rt->val = rt->lc->val + rt->rc->val;
}

快速线性筛选法

质数,欧拉函数及莫比乌斯函数的快速线性筛选法,时间复杂度 $O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int MAXN = 100000;
int phi[MAXN + 10], prime[MAXN + 10], mu[MAXN + 10], tot;
bool vis[MAXN + 10];
inline void init() {
mu[1] = phi[1] = 1;
for (register int i = 2; i <= MAXN; i++) {
if (!vis[i]) prime[++tot] = i, phi[i] = i - 1, mu[i] = -1;
for (register int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j], mu[i * prime[j]] = 0;
break;
} else phi[i * prime[j]] = phi[i] * (prime[j] - 1), mu[i * prime[j]] = -mu[i];
}
}
}

AA树学习笔记

$AA$ 树是 $Arne Andersson$ 教授在他的论文 $”Balanced search trees made simple”$ 中介绍的一个红黑树变种,设计的目的是减少 $RB$ 树考虑的 $cases$。

大小写转化的奇怪技巧

通常情况下,我们可以使用函数 $toupper()$ 和 $tolower()$ 来实现字母大小写的转化,但在需要常数优化的情况下,这是较慢的。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×