Arendelle Royal Library

线段树：竞赛数据结构的基石无论是纯粹的数据结构题还是数据结构优化其他算法，线段树都是绕不开的一个东西。 线段树的基本思想事实上十分简单：分治。把大区间拆成小区间，能延迟操作就延迟操作，这就是线段树的基本思想。它解决的问题也很简单：区间查询，区间修改。 在数据结构题以外，我们依然可以见到线段树的身影，包括但不限于树剖维护树上问题、优化dp状态转移、优化dijkstra等。这些我们都将在下面见到例题。 当然，在面对一些其他问题时，线段树的功能就有些捉襟见肘了，这种时候我们通常会考虑另一个几乎万能的数据结构：平衡树。当然平衡树也不是真的万能，有些问题（例如在线带修改区间第k大）单独的平衡树和线段树都无法解决，于是我们又会请出重量级的数据结构：树套树。不过，这些都超出了我们现在的讨论范围。这篇文章的重心依然会放在线段树上。 最简单的线段树1就不赘述了。我相信在座的各位都可以十分流畅的写出一颗支持基础操作的线段树。至于线段树2，我们将在后面的双半群模型部分详细讨论这个问题及其加强版。 这里提一个建议：找到一个自己最喜欢的线段树的写法，然后就一直沿用这个写法，这样考场上不容易写错。 关于线段树基 ...

本文根据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个字节一行排列成矩阵，比如说 ...