Arendelle Royal Library

本文根据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 CompilerInstance());，这个东西是整个编译流程的核心。接下来基本上是在处理输入参数和判断异常，直到250行ExecuteCompilerInvocation(Clang.get())。 这个函数定义在clang/include/clang/FrontendTool/Utils.h里，实现在clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp里。这里很多代码也是在处理各种边界条件以及加载插件之类的事 ...

关于树链剖分首先，需要知道一个事情：树链剖分其实很简单。 其次，需要知道另一个事情：树链剖分能解决的只有静态树上问题。如果你需要解决动态树（指的是树的结构发生变化）的问题，那么你需要的应该是Link-Cut Tree 那么树剖可以解决什么问题呢？ 事实上，单单一个树剖能解决的问题不多，但是由于树剖的一些优秀性质，使得我们可以通过树剖+数据结构（例如线段树）的方式，实现： 子树查/改 路径查/改 这无疑是非常有用的。 另一方面，对于某些类型的树形dp，我们也可以使用树剖优化。 需要注意的是，通常来讲认为树剖分为两类，第一类是重链剖分，通常与线段树结合，另一类是长链剖分，通常用于优化dp。还有一类特殊的，有时被称作实链剖分，只用于LCT当中。 那么我们开始。 重链剖分例题：P3384 首先我们要知道重链剖分是什么。在此之前，有一个概念叫重儿子。故名思义，就是最重的儿子。对于每一个节点，他的所有儿子中，对应的子树中节点个数最多的儿子，被称作一个节点的重儿子。（其实就是最重的儿子） 那么显然，除了叶子节点以外，每个节点有且只有一个重儿子。我们把所有的节点与他们的重儿子连起来，就可以把整棵树 ...

什么是二叉搜索树？讲二叉搜索树之前，首先得知道他解决了什么问题： 查找数列第k大 查询一个数的排名rank 插入一个数 删除一个数 显然，一个每次操作后都sort一遍的数组就可以解决这个问题。但是这显然不是我们想要的答案：他太慢了。 那么有什么快一些的方案呢？有，就是二叉搜索树 Binary Search Tree。 首先，顾名思义，二叉搜索树首先是一棵二叉树。 那么二叉搜索树BST又有什么和普通二叉树不一样的性质，使得他可以“搜索”的呢？ 我们可以先回顾一个有点相似的东西叫做堆。我们知道，堆是一棵完全二叉树，他满足每一个节点都比他的所有儿子要大（大根堆）。依靠这个性质，我们可以很轻松地实现求一个序列中最大的数，并且实现快速的增和删操作。 但是，很显然，仅仅依靠堆我们是没办法实现上面的操作的。这是由于堆的性质不够强：他只要求父亲比儿子大，却并没有规定左右子树之间的大小关系。但是我们可以修改一下这颗树的性质，改成这样：每一个节点，左子树都小于自己，右子树都大于自己。——这就是BST了。 容易发现，BST的中序遍历，就是排序后的原序列。我们也可以从根节点开始，递归的向左右子树搜索， ...

题目大意已知正整数$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)\\ &=x^2-\sum^{x}_{i=1}(x\ mo ...

前置知识：线段树 基本原理主席树，又名可持久化权值线段树，是一种可持久化线段树。当然，很多地方通常也会用主席树来指代可持化线段树。它是最常见的可持久化数据结构之一。 要想实现线段树的可持久化，有一个很笨的方法：每次更改都复制一份进行修改。很显然，这在时空上效率都极其低下。我们要考虑如何节省时间和空间。此时我们很容易想到：只记录修改的节点。由于线段树的深度是$O(\log n)$的，所以每次单点修改最多修改$O(\log n)$的节点，因此也可以在$O(\log n)$的空间内实现历史记录。 这个时候可持久化线段树的结构就很容易想到了。由于我们增加了很多节点，因此我们不能用常规线段树用两倍表示孩子的做法，而应该使用类似动态开点线段树的策略，在节点里面保存左右儿子的编号。 接下来我们考虑怎么实现单点修改和区间查询。在可持久化线段树上实现区间修改是比较困难的，之后再考虑。 建树 & 区间查询其实建树和区间查询的代码和正常的线段树一模一样 从图上我们可以看出来，假如说我们从某一个根节点开始向下深搜，得到的树就是一棵正常的线段树，因此我们只要从某一个根节点开始，和普通线段树一样向下查询 ...

平板电视：比 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>// 类似bits/stdc++.h// ...

AES有多种加密方式和填充方式。 加密方式分组密码加密方式主要有7种：ECB，CBC，CFB，OFB和CTR，这五种方式将在下面一一讲解。 0. 初始化向量 / IV在讲加密模式之前首先得要了解一个概念：初始化向量 (IV) 在除ECB以外的所有加密方式中，都需要用到IV对加密结果进行随机化。在使用同一种加密同一个密钥时不应该使用相同的IV，否则会失去一定甚至全部的安全性。如果到这里还不明白的话没关系，后面还会继续讲到。 1. 电子密码本 / ECB 这里$CIPH$指AES加密算法，$CIPH^{-1}$指AES解密算法。 这个很好理解：将明文简单的按照128bit为一个分块进行切割，把每个分块分别进行AES加密，然后再将得到的密文简单的拼接一下即可。 注意到AES加密只能加密128bit的分块，那问题就产生了：如果明文的长度不是128bit的倍数，就会存在一个分块不足128bit，那如何对这个分块进行加密？ 别慌，你想到的问题别人早就想到了。为了解决这个问题，我们发明了一种叫做填充的东西，这将会在后面具体讲解。OFB和CTR不需要填充！ ECB模式有一个显著的安全问题：如果使用相 ...

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 F,\ ...

本系列长期更新，全部更新完后会同步到知乎专栏 AES算法，一般指Rijndeal算法 简介AES原本指的是一套标准FIPS 197，而AES算法一般指分组大小为128bits的Rijndeal算法，由比利时学者Joan Daemen和Vincent Rijmen提出。 AES与Rijndeal的区别AES仅指分段为128位的Rijndeal算法，两种算法对比如下： (Nr表示循环轮数，Nb表示分组大小，Nk表示密钥长度，Nb和Nk单位都是32bits) Nr Nb=4 (AES) Nb=6 Nb=8 Nk=4 10 (AES-128) 12 14 Nk=6 12 (AES-192) 12 14 Nk=8 14 (AES-256) 14 14 加密总体流程 图片来自链接，这张图是AES-128的流程，AES-192和AES-256除了加密轮数和密钥长度以外都是一样的 AES加密的整个过程是在一个4×4的字节矩阵上运作的，这个字节矩阵称作state。这个字节矩阵是由当前明文块处理得到的，简而言之就是把当前的16个字节按照4个字节一行排列成矩阵，比如说 ...

MD5即Message-Digest Algorithm 5, 信息学中使用广泛的哈希算法 MD5简介MD5即Message-Digest Algorithm 5, 信息学中使用广泛的哈希算法 这个算法具有很多性质: 压缩性: 对于任意长度的输入, 输出长度总是相同的 容易计算: 线性时间复杂度 抗修改性: 对原数据的一点点修改都会导致最终结果的巨大变化 抗碰撞性: 已知原数据和MD5值很难生成与原数据不同但MD5值相同的数据 MD5可以生成任意一个文件的“数字指纹”，对文件的微小改动都会直接导致数字指纹的巨大变化。 注：MD5加密中文需要使用UTF-8编码，但Windows下默认是GBK编码，两种编码得到的结果是不一样的 加密步骤填充MD5中，首先要对信息进行填充，先填充一个1，后面都填充0，使得信息的长度 $len \equiv 448 \pmod{512}$ ，即 $len\bmod 512 = 448$。为什么要求模出来是448呢？因为448=512-64，而填充完后后面还要再填上64位的原数据长度，如果超出64位则填充原数据长度的后64位，这样可以使得最终的数据长度 ...