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...