1.1 计算机发展历程(*)第一台电子数字计算机: ENIAC(1946) 硬件的发展 发展阶段 时间 逻辑元件 速度(次/秒) 内存 外存 第一代 1946-1957 电子管 几千-几万 汞延迟线、磁鼓 穿孔卡片、纸带 第二代 1958-1964 晶体管 几万-几十万 磁芯存储器 磁带 第三代 1964-1971 中小规模集成电路 几十万-几百万 半导体存储器 磁带、磁盘 第四代 1972-现在 大规模、超大规模集成电路 上千万-万亿 半导体存储器 磁盘、磁带、光盘、半导体存储器 1.2 计算机硬件的基本组成计算机硬件的基本组成冯·诺依曼计算机 采用“存储程序”的工作方式 计算机由五大部件组成 指令和数据以同等地位存于存储器，可按地址寻访 指令和数据用二进制表示 指令由操作码和地址码组成 以运算器为中心 现代计算机 各个硬件的工作原理主存储器的基本组成 存储体 MAR（Memory Address Register, 存储地址寄存器） MDR（Memory Data Register, 存储数据寄存器） 现在的计算机通常把MAR、M ...

5.1 传输层提供的服务端口的作用 通过**“端口号”**标识本主机的一个特定进程 每台主机的端口号是相互独立的 TCP、UDP两种协议的端口号也是相互独立的 TCP或UDP协议，通过Socket 套接字={IP地址：端口号}，唯一标识网络中的一台主机上的一个应用进程 端口号的分类 服务器使用的端口号 熟知端口号（0~1023） 登记端口号（1024~49151） 客户端使用的端口号——短暂端口号 49152~65535 功能 实现端到端（进程到进程）的通信 复用和分用 复用（从上到下） 在发送数据的时候，同一台主机上的多个进程可以使用同一个传输协议 分用（从下到上） 在接收数据的时候，传输层可以把数据正确交付到目的进程 差错检测 TCP检测出差错后丢弃数据，并通知发送方重传 UDP检测出错误后直接丢弃，且不通知发送方 向应用层提供两种服务 面向连接的、可靠的端到端传输服务（TCP）——确保数据正确/完整，但开销大、实时性差 无连接的、不可靠的端到端传输服务（UDP）——数据可能出错/丢失，但速度快、开销小 ...

4.1 网络层的功能网路层为传输层提供服务，将传输层的数据封装成**“IP数据报”。网络中的路由器根据IP数据报首部中的源IP地址**、目的IP地址进行“分组转发”。因此，网络层实现了**“主机到主机”**的传输。 数据链路层为网络层提供服务，将网络层的 **IP数据报（分组）**封装成帧，传输给下一个相邻结点。 异构网络互联 异构：每个网络的拓扑结构不同、物理层&链路层的实现不同、主机类型也各不相同 重要的设备：路由器（Router） 注：在TCP/IP文献中，路由器也称为 网关（Gateway） 路由与转发 路由 各个路由之间相互配合，规划IP数据报（分组）的最佳转发路径 注：各个路由器需要运行“路由协议”，最终生成各自的“路由表” 转发 一台路由器，根据自己的“转发表”，将收到的IP数据报从合适的接口转发出去 注：转发表 = 精简版路由表。更精简的数据结构有助于快速检索 数据网络提供两种服务：虚电路、数据报 虚电路在虚电路方式中，当两台计算机进行通信时，应当先建立网络层的连接，也就是建立一条逻辑>上的虚电路，连接一旦建立，就固定 ...

3.1 数据链路层的功能 数据链路层 使用 物理层 的 “比特传输” 服务，为 网络层 提供服务 物理链路：传输介质（0层）+物理层（1层）实现了相邻结点之间的 “物理链路” 。 逻辑链路：数据链路层需要基于 “物理链路”，实现相邻结点之间逻辑上无差错的 “数据链路（逻辑链路） 3.2 组帧 主要问题： 帧定界：确定帧的边界 透明传输：接收方要能够取出 ”帧定界“ 的附加信息，把帧恢复原貌。 方法有： 字符计数法 字节填充法 零比特填充法 违规编码法 违规编码法 利用物理层插入“违规信号”，标记帧的开头、结尾 3.3 差错控制 检错编码 奇偶校验 信息位：帧的“数据部分” 校验位（冗余位）：为了给帧的“数据部分”检错/纠错而附加的一些冗余比特 奇校验：其整个校验码（有效信息位和校验位）中“1”的个数为奇数 偶校验：其整个校验码中“1”的个数为偶数 校验位通过判断其余部分“1”的个数进行补充，使得符合奇校验码或者偶校验码。 缺点：无法检测出偶数位错误、无纠错能力 循环冗余校验 ...

物理层任务：实现相邻节点之间比特的传输。 2.1 通信基础基本概念信源：信号的来源（数据的发送方） 信宿：信号的”归宿“（数据的接收方） 信道： 信号的通道 信号：数据的载体 数字信号，信号值是离散的 模拟信号，信号值是连续的 每一个信号就是一个码元 ​ 如果一个码元（一个信号），可能有4种状态，那么可以称其为4进制码元。如果有 $K$ 种，则一个码元可携带 $\log_{2}{K}\ bit$ 的数据 。波特率也是速率的一种表现方式，其单位为 $码元/s$ 或 $波特$ 。 信道的极限容量带宽：信道允许通过的信号频带范围，单位：Hz 噪声：对信道产生干扰，影响信道的数据传输效率。 奈奎斯特定理：对于一个理想低通信道（没有噪声、带宽有限的信道），极限波特率 = $2W$ (单位：波特) 香农定理：对于一个有噪声、带宽有限的信道，极限比特率 = $W \log_2{(1+\frac{S}{N})}$ ，其中 $\frac{S}{N}$ 为信噪比。 ​ 信噪比作为数值往往很大，可以用 $db$（分贝）为单位，此时信噪比为 $10\log_{10}{\f ...

1.1 计算机网络概述计算机网络的概念​ 计算机网路是一个将众多分散的、自洽的计算机系统，通过通信设备与线路连接起来，有功能完善的软件实现资源共享和信息传递的系统。 ​ 计算机网络(简称 网络)：由若干**结点（node）和链接这些结点的链路（link）**组成。结点可以是计算机、集线器、交换机、路由器等。 ​ 把两个或多个计算机网络互相连接起来，形成规模更大的计算机网络，也可称”互连网”。 ​ 互联网(因特网)指当前全球最大的、开放的、由众多网络和路由器互连而成的特定计算机网络，它采用了TCP/IP协议族作为通信规则。 注意：家用路由器往往是路由器+交换机+其他功能 计算机网络的组成​ 从组成部分看，计算机网络主要由硬件、软件、协议三大部分组成。 ​ 从工作方式看，计算机网络(这里主要指Internet，互联网) 可分为边缘部分和核心部分。边缘部分由互联网上的供用户直接使用的主机组成，用来进行通信和资源共享;核心部分由大量网络和连接这些网络的路由器组成，它为边缘部分提供连通性和交换服务。 ​ 从功能组成上看，计算机网路由通信子网和资源子网组成。 计算机网络的功能 数据 ...

珂朵莉树 参考资料: 珂朵莉树/颜色段均摊 - OI Wiki 珂朵莉树（Chtholly Tree），又称ODT。源自 CF896C。 这个名称指代的是一种使用 平衡树 或 链表 维护「颜色段均摊」的技巧，而不是一种特定的数据结构。其核心思想是将指相同的一段区间合并成一个结点处理。相较于传统的线段树等数据结构，对于含有区间覆盖的操作问题，珂朵莉树可以更加方便地维护每个被覆盖区间的值。 实现（std::set） 结点类型 123456struct Node_t{ int l,r; mutable int v; //mutable能突破 const 的限制，使变量永远可变 Node_t(const int &il,const int &ir,const int &iv):l(il),r(ir),v(iv){} //构造函数 bool operator<(const Node_t &o) const {return l<o.l;}}; ...

归并排序 定义 归并排序（merge sort）是高效的基于比较的稳定排序算法 性质 归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 \(O(nlogn)\)，空间复杂度为 \(O(n)\)。 归并排序可以只使用 \(O(1)\) 的辅助空间，但为便捷通常使用与原数组等长的辅助数组。 过程 合并 归并排序最核心的部分是 合并（merge）过程：将两个有序的数组 \(a[i]\) 和 \(b[i]\) 合并为一个有序数组 \(c[k]\)。 从左往右枚举 \(a[i]\) 和 \(b[j]\)，找出最小的值并放入数组 \(c[k]\)；重复上述过程直到 \(a[i]\) 和 \(b[j]\) 有一个为空时，将另一个数组剩下的元素放入 \(c[k]\) 。 为保证排序的稳定性，前段首元素小于或等于后端首元素时（\(a[i]\leq b[j]\)）而非小于时（\(a<b\)），就要作为最小值放入 \(c[k]\) 数组实现： 12345678910111213141516void merge(const int *a, i ...

参考资料：倍增 - OI Wiki 倍增 定义 倍增法（binary lifting），即“成倍增长”的含义。我们在进行递推时，如果状态空间很大，那么通常的线性递推无法满足空间和时间复杂度的要求。那么，我们可以通过成倍增长的方式，只递推状态空间中在 \(k\) 的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过k的一元多项式之和得到。所以使用倍增算法也要求我们递推的问题的状态空间关于 \(k\) 的次幂具有可划分性。通常情况下 \(k\) 取 \(2\) （这样每项的系数要么为 \(1\) ，要么为 \(0\) ） 应用 RMQ问题 RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值 。使用 ST表 是基于倍增思想的 RMQ问题 求解方式 树上倍增求LCA 求最近公共祖先的倍增解决方式