Tiny Cobalt 开发日志
这里是Tiny Cobalt的开发日志。尽量持续更新。 初期工作：框架的搭建两年前和 AndyShen 最初决定写自己的编译器的时候，打算的技术方案是 CMake 作为构建系统，标准定在 C++17 。24年12月初的时候我决定重新开工，此时各大编译器对于 C++20 的支持已经逐渐完善了，此外 xmake 构建系统也已经比当年更加完善，因此重新启动 Cobalt 项目的时候，我决定采用 xmake 作为编译系统。这带来的一大好处是便捷的包管理，另一个好处是可以避免复杂的 cmake 脚本，可以注意力集中在代码上而不用折腾太多依赖。 最开始，我们打算基于 std::variant 作为运行时多态的实现，此外也引入了微软的 proxy 库作为备用方案，目的是为了尝试着探索 C++ 传统的继承+虚函数方案以外的其他多态方案。然而，在实现的过程中，我们发现 std::variant 并不能完全实现我们需要的多态，此外它与 proxy 的兼容性也一般。因此，我们决定全面改用 proxy 。在 Utility.h 中可以看到一些早期代码的残留。后来在开发过程中发现了 proxy...
关于线段树：从入门到入土
...
LLVM源码阅读 笔记
本文根据LLVM 15.0.7版本代码更新 clang主入口clang 目录下貌似没有找到一个main函数，推测是在编译时生成。目前看来，clang的主入口是在clang/tools/driver/driver.cpp下面的clang_main函数。这里很多乱七八糟的边界处理，并不重要，一路可以追溯到同一个目录下面的cc1_main.cpp里的cc1_main函数。 在cc1_main里同样有很多异常处理。在函数开头构造了一个std::unique_ptr<CompilerInstance> Clang(new...
树链剖分
关于树链剖分首先，需要知道一个事情：树链剖分其实很简单。 其次，需要知道另一个事情：树链剖分能解决的只有静态树上问题。如果你需要解决动态树（指的是树的结构发生变化）的问题，那么你需要的应该是Link-Cut...
关于BST：你所需要知道的一切
什么是二叉搜索树？讲二叉搜索树之前，首先得知道他解决了什么问题： 查找数列第k大 查询一个数的排名rank 插入一个数 删除一个数 显然，一个每次操作后都sort一遍的数组就可以解决这个问题。但是这显然不是我们想要的答案：他太慢了。 那么有什么快一些的方案呢？有，就是二叉搜索树 Binary Search...
连续正整数的因子和之和问题
题目大意已知正整数$x<y$, 求: \sum^{y}_{i=x} \sum _{j|i} j数据范围： 对于$50\%$的数据，有：$0<x,y<=1\times10^6$ 对于$100\%$的数据，有：$0<x,y<=2\times10^9$ 保证结果在long long范围内 题目分析题面非常的直白。令$\sigma(x)=\sum {i|x}x, D(x)=\sum^x{i=1}\sigma(i)$，那么显然，我们所求的东西就是$D(y)-D(x-1)$。 接下来的问题就是，如何快速的求$D(x)$。 显然我们有一个$O(n)$的解法，就是枚举每一个数，求区间内他的倍数出现次数，得到$D(x)=\sum^x_{i=1}i\lfloor\frac{x}{i}\rfloor$。但这显然无法满足全部数据的要求。我们需要更快的解法。在此我们给出一个$O(\sqrt{n})$的解法。 先给出一个结论： \begin{align*} D(x)&=\sum^{x}_{i=1}\sigma(i)\\ ...
算法学习笔记：主席树
前置知识：线段树 基本原理主席树，又名可持久化权值线段树，是一种可持久化线段树。当然，很多地方通常也会用主席树来指代可持化线段树。它是最常见的可持久化数据结构之一。 要想实现线段树的可持久化，有一个很笨的方法：每次更改都复制一份进行修改。很显然，这在时空上效率都极其低下。我们要考虑如何节省时间和空间。此时我们很容易想到：只记录修改的节点。由于线段树的深度是$O(\log n)$的，所以每次单点修改最多修改$O(\log n)$的节点，因此也可以在$O(\log n)$的空间内实现历史记录。 这个时候可持久化线段树的结构就很容易想到了。由于我们增加了很多节点，因此我们不能用常规线段树用两倍表示孩子的做法，而应该使用类似动态开点线段树的策略，在节点里面保存左右儿子的编号。 接下来我们考虑怎么实现单点修改和区间查询。在可持久化线段树上实现区间修改是比较困难的，之后再考虑。 建树 &...
pbds食用教程
平板电视：比 STL 还 STL ——来自 luogu 某佬 Intro 前言pb_ds的主体部分在__gnu_pb_ds命名空间下，使用前需要using namespace __gnu_pbds WARNING: NOIP 评测的时候可能不允许使用using namespace __gnu_pbds。 头文件如下： 12345#include <ext/pb_ds/assoc_container.hpp> // 各种类的定义 必须引用#include <ext/pb_ds/tree_policy.hpp> // tree#include <ext/pb_ds/hash_policy.hpp> // hash#include <ext/pb_ds/trie_policy.hpp> // trie#include <ext/pb_ds/priority_queue.hpp> // priority_queue 或者 123#include <bits/extc++.h>//...
AES加密(3)：AES加密模式与填充
AES有多种加密方式和填充方式。 加密方式分组密码加密方式主要有7种：ECB，CBC，CFB，OFB和CTR，这五种方式将在下面一一讲解。 0. 初始化向量 / IV在讲加密模式之前首先得要了解一个概念：初始化向量 (IV) 在除ECB以外的所有加密方式中，都需要用到IV对加密结果进行随机化。在使用同一种加密同一个密钥时不应该使用相同的IV，否则会失去一定甚至全部的安全性。如果到这里还不明白的话没关系，后面还会继续讲到。 1. 电子密码本 /...
AES加密(2)：GF(256)域
GF(256)域是一个有限域，在密码学中非常常用 什么是有限域/伽罗瓦域(Galois Field)?顾名思义，有限域就是含有有限个元素的域。 既然是含有有限个元素的域，那么关键点就在于有限和域两个概念。 首先我们看一下域的定义(来自维基百科)): 在抽象代数中，域(Field)是一种可以进行加，减，乘，除（除了除以加法单位元“0”）运算的代数结构。域的概念是数域以及四则运算的推广。 在这里加法和乘法并不是我们所熟悉的加法和乘法。我们把这个域记作$F$，其中加法和乘法满足以下几种特性： \begin{align*} &(1)\qquad\forall a,b\in F,\ a+b\in F,\ a\cdot b\in F \\ &(2)\qquad\forall a,b\in F,\ a+b=b+a,\ a\cdot b=b\cdot a \\ &(3)\qquad\forall a,b,c\in F,\ (a+b)+c=a+(b+c),\ (a\cdot b)\cdot c=a\cdot (b\cdot c) \\ &(4)\qquad\forall a,b,c\in...