我并没有去打 CF，然后就跑去打第一场 AtCoder 刷水…

链接

AtCode BC061

求解最小费用流的算法有很多，如增广路算法(SPFA)，消圈算法，zkw 算法，Primal Dual 算法及网络单纯形，其中消圈算法和网络单纯形较为通用但速度不够快或编程复杂度过高，SPFA 和 zkw 在不同的图上各有所长，这里介绍不容易被卡掉的 Primal Dual 算法。

注意: Primal Dual 算法也不能适用于存在负圈的图。

写二分被卡 T 了，赶紧来补一补 01-分数规划的 Dinkelbach 算法…

一些最大流和最小割题目…
填坑中…

求解网络流最大流问题有很多算法，ISAP 是图论求最大流的算法之一，它很好的平衡了运行时间和程序复杂度之间的关系，因此性价比很高。
而 HLPP 算法理论复杂度十分优秀，在实际运用中由于上界更紧而并不一定会快于 ISAP，但是 HLPP 在分层图中表现十分出色，甚至比在分层图上复杂度为 $O(n^2)$ 的 MPM 算法还快。
这里简单的给出这两个算法的思想以及代码实现。

小Q的棋盘

小Q 正在设计一种棋类游戏。在小Q设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 $V$ 个格点，编号为 $0,1,2, \cdots, V-1$，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小Q 现在想知道，当棋子从格点 $0$ 出发，移动 $N$ 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

复习 Tarjan 算法以及一些常见的应用。

给你一棵 $n$ 个点的无根树。

树上的每条边具有颜色。一共有 $m$ 种颜色，编号为 $1$ 到 $m$。第 $i$ 种颜色的权值为 $c_i$。

对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划

分成若干个相同颜色段。定义路径权值为颜色序列上每个同颜色段的颜色权值之和。

请你计算，经过边数在 $l$ 到 $r$ 之间的所有简单路径中，路径权值的最大值。

矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才有意义，这里给出常见的几种实现方式，以及它们性能的比较，然后再给出几种优化，这里的优化是针对 $O(n^3)$ 朴素矩阵乘法的优化，因为朴素算法更容易利用硬件进行优化。

永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。

并查集 (Union-Find Set) 是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图,求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。

算术天才 ⑨ 非常喜欢和等差数列玩耍。

有一天，他给了你一个长度为 $n$ 的序列，其中第 $i$ 个数为 $a[i]$。

他想考考你，每次他会给出询问 $l, r, k$，问区间 $[l, r]$ 内的数从小到大排序后能否形成公差为 $k$ 的等差数列。
当然，他还会不断修改其中的某一项。

为了不被他鄙视，你必须要快速并正确地回答完所有问题。

注意：只有一个数的数列也是等差数列。

共有 $m$ 部电影，编号为 $1 \sim m$，第 $i$ 部电影的好看值为 $w[i]$。

在 $n$ 天之中（从 $1 \sim n$ 编号）每天会放映一部电影，第 $i$ 天放映的是第 $f[i]$ 部。

你可以选择 $l,r(1 \leq l \leq r \leq n)$，并观看第 $l,l+1,\cdots,r$ 天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

前几天看 ZKW 线段树，ZKW 说用 Trie 式方法可以解决空间问题从而使 ZKW 线段树能当平衡树用，和 wuvin 讨论了一下发现这么做，时间要么只能优化插入，要么只能优化第 $k$ 大。
想了想，感觉可以将 Trie 树，ZKW 线段树，32 叉线段树，以及压位计算结合起来，这样就得到了一个空间消耗比 32 叉线段树小得多，时间效率比 ZKW 线段树快，结构类似 Trie 的神奇数据结构，常数可是比 VEB 小了太多….
实测效率相当高，若用数组实现，空间消耗为值域大小。

听说此题又卡线段树，没事我们还有 ZKW 线段树……
ZKW 线段树在代码长度(不打标记时)和时间上较普通线段树都有较大优势，在 RMQ 甚至会出现喜闻乐见的 $O(\text{ log }n)$ 踩 $O(\text{ log log }n)$ 甚至 $O(1)$ 算法。
这里记录 ZKW 线段树的基本操作以及较为通用的区间操作(非差分而是标记下传)

乘法逆元是数论中重要的内容，也是 OI 中常用到的数论算法之一。

定义

在 $\text{mod p}$ 意义下我们把 $x$ 的乘法逆元写作 $x^{-1}$
$$x \times x^{-1} \equiv 1 \text{ (mod p)}$$

这里重新复习一下扩展欧几里得算法的常见应用。

普通快速幂在面对大量数据或单个够大数据时效率很低，这个时候我们就需要十进制快速幂，而如果模数是 long long 以内的数，我们可以用快速幂思想 $O(\text{log n})$ 完成快速乘，但我们其实可以 $O(1)$ 完成。

补档计划

明日は明日の风が吹く，调整状态，进入新的征程，好好补一些东西…

SCOI 2017 总结

SCOI 2017 结束了，完挂….
在这里还是先祝贺 wuvin 顺利 A 队，ihopenot 顺利翻盘，为 zyqn 默哀…

最短路及其应用

先挖坑…

一个长度为 $ n $ 的大数，用 $ S_1S_2S_3 \ldots S_n $表示，其中 $ S_i $ 表示数的第 $ i $ 位，$ S_1 $ 是数的最高位，告诉你一些限制条件，每个条件表示为四个数 $( l_1, r_1, l_2, r_2 )$，即两个长度相同的区间，表示子串 $ S_{l_1}S_{l_1 + 1}S_{l_1 + 2} \ldots S_{r_1} $ 与 $ S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots S_{r_2} $ 完全相同。

比如 $ n = 6 $ 时，某限制条件 $ (l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6) $，那么 $ 123123 $,$ 351351 $ 均满足条件，但是 $ 12012 $,$ 131141 $ 不满足条件，前者数的长度不为 $ 6 $，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名（可能没有）下线，除 $1$ 名大头目外其余 $n - 1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严，每名情报员只能与自己的上,下线联系，同时，情报网络中任意两名情报员一定能够通过情报网络传递情报。

1. 搜集情报：指派 $T$ 号情报员搜集情报
2. 传递情报：将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员

情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为0；-旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加1点危险值（开始搜集情报的当天危险值仍为0，第2天危险值为1，第3天危险值为2，以此类推）。传递情报并不会使情报员的危险值增加。为了保证传递情报的过程相对安全，每条情报都有一个风险控制值C。余特公司认为，参与传递这条情报的所有情报员中，危险值大于C的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。

作为一个先学工程的蒟蒻 oier，也就只能在卡常上有一些技巧了……

然而我太弱，并没有去成 WC，虽然感觉 T2 卡三级缓存不是应该很好卡吗？

这里总结松爷的一些技巧和记录一些其他技巧及一些实际例子。

有 $K$ 个棋子在一个大小为N×N的棋盘。一开始，它们都在棋盘的顶端，它们起始的位置是 $(1, a_1),(1, a_2),…,(1, a_k)$，它们的目的地是 $(n, b_1), (n, b_2),…,(n, b_k)$。

一个位于 $(r,c)$ 的棋子每一步只能向右走到 $(r, c + 1)$ 或者向下走到 (r + 1, c)$。

我们把 $i$ 棋子从 $(1, a_i)$ 走到 $(n, b_i)$ 的路径记作 $p_i$。

你的任务是计算有多少种方案把 $n$ 个棋子送到目的地，并且对于任意两个不同的棋子 $i,j$，使得路径 $p_i$ 与 $p_j$ 不相交（即没有公共点）。

Ben 最近学习了二进制信息。一条二进制信息由 $n$ 个二进制码组成，第 $i$ 个二进制码记为 $s_i$ 。二进制码就是一个只包含 ′0′ 和 ′1′ 的字符串。一条二进制信息被称为“漂亮的二进制信息”当且仅当对于任意的 $i \neq j$，$s_i$ 都不是 $s_j$ 的前缀。二进制码 $x$ 是二进制码 $w$ 的前缀当且仅当存在一个二进制码 $y$ （长度可以为 $0$），使得 $xy = w$ ，例如 $x = 11$ 是 $w = 110$ 的前缀，$x = 0100$ 是 $w = 0100$ 的前缀。

Ben找到一张纸，上面写着二进制信息。可是，这张纸有点旧了，有些字符看不清。但是很幸运，每个二进制码都只包含最多一个看不清的字符。

Ben 想知道这 $n$ 个二进制码能否表示一条“漂亮的二进制信息”。也就是说，是否存在一种方案，用 ′0′ 或 ′1′ 替换那些看不清的字符，使得这条信息变为漂亮的二进制信息。

CJB 天天要跟妹子聊天，可是他对微信的加密算法表示担心：“微信这种加密算法，早就过时了，我发明的加密算法早已风靡全球，安全性天下第一！”

CJB 是这样加密的：设 CJB 想加密的信息有 $m$ 个字节。首先，从网上抓来一张 $n(n \geq m)$ 个字节的图片，分析里面的每个字节(byte)。每个字节有 $8$ 位(bit)二进制数字。他想替换掉某些字节中最低位的二进制数字，使得这张图片中，连续 $m$ 个字节恰为他想加密的信息。这样，图片看起来没什么区别，却包含了意味深长的信息。

很显然，不是所有的图片都能让 CJB 加密他那 $m$ 个字节的信息。他想请你帮忙写个程序判断这张图片是否能加密指定的信息。如果可以加密，则 CJB 要求改变最少的字节数。如果仍有多种解，他希望信息在图片中的位置越前越好。

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第i个装置时，它会往后弹 $k_i$ 步，达到第 $i + k_i$ 个装置，若不存在第 $i + k_i$ 个装置，则绵羊被弹飞。绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

在 2111 年，第 128 届全国青少年信息学奥林匹克冬令营前夕，Z 君找到了 2015 年，第 32 届冬令营的题目来练习。

他打开了第三题「未来程序」这道题目：

「本题是一道提交答案题，一共 10 个测试点。

对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。

遗憾的是这些程序都效率极其低下，无法在比赛的 5 个小时内得到输出。」

Z 君想了一下，决定用 2111 年的计算机来试着运行这个题目，但是问题来了，Z 君已经找不到 96 年前的那次比赛的测试数据了 \cdots \cdots

没有给出输入数据的提交答案题就不成其「提交答案题」之名，为了解决这个问题，Z 君决定将这个题目改造成传统题。

Z 君知道 96 年前的计算机的性能比现在差多了，所以这道题的测试数据中，输入数据的规模被设计成很小，从而，做这道题的选手只需要暴力模拟源代码的工作流程就可以通过它。

现在这道题摆到了你的面前。

本题是一道传统题，一共有 10 个测试点。

对于每个测试点，你的程序会得到一段程序的源代码和这段程序的输入。你的程序需要运行这段程序，并输出这段程序的输出。

一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：

+ $u$ $v$ $c$：将u到v的路径上的点的权值都加上自然数c；

- $u_1$ $v_1$ $u_2$ $v_2$：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$，保证操作完之后仍然是一棵树；

* $u$ $v$ $c$：将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$；

/ $u$ $v$：询问 $u$ 到 $v$ 的路径上的点的权值和，求出答案对于 $51061$ 的余数。

辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

Link-Cut Tree学习总结

在数据结构中有一类问题叫做动态树问题（DynamicTree），它会要求你对一颗树进行切割和拼接，然后再在上面维护传统的数据结构能维护的值，为了完成这一类问题，就有了很多相应的算法来解决这类问题，Link-Cut Tree 就是其中一种比较方便实用的算法。

这里保存一些后缀自动机常见应用和例题，不断完善中，更多的还是看补档计划吧……

给定 $n$ 个整数 $A_1,A_2,A_n$ ，求有多少个三元组 $(i,j,k)$ 满足 $1 \leq i < j < k \leq n$ 且 $A_j-A_i=A_k-A_j$ 。

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is simple, for two given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Once upon a time there was a famous actress. As you may expect, she played mostly Antique Comedies most of all. All the people loved her. But she was not interested in the crowds. Her big hobby were beads of any kind. Many bead makers were working for her and they manufactured new necklaces and bracelets every day. One day she called her main Inspector of Bead Makers (IBM) and told him she wanted a very long and special necklace.

The necklace should be made of glass beads of different sizes connected to each other but without any thread running through the beads, so that means the beads can be disconnected at any point. The actress chose the succession of beads she wants to have and the IBM promised to make the necklace. But then he realized a problem. The joint between two neighbouring beads is not very robust so it is possible that the necklace will get torn by its own weight. The situation becomes even worse when the necklace is disjoined. Moreover, the point of disconnection is very important. If there are small beads at the beginning, the possibility of tearing is much higher than if there were large beads. IBM wants to test the robustness of a necklace so he needs a program that will be able to determine the worst possible point of disjoining the beads.

The description of the necklace is a string A = a1a2 … am specifying sizes of the particular beads, where the last character am is considered to precede character a1 in circular fashion.

The disjoint point i is said to be worse than the disjoint point j if and only if the string aiai+1 … ana1 … ai-1 is lexicografically smaller than the string ajaj+1 … ana1 … aj-1. String a1a2 … an is lexicografically smaller than the string b1b2 … bn if and only if there exists an integer i, i <= n, so that aj=bj, for each j, 1 <= j < i and ai < bi

后缀自动机学习总结

前置技能

有限状态自动机

有限状态自动机 DFA，功能就是识别字符串，令一个自动机 $A$，若能识别字符串 $S$，就记为 $A(S) = true$，否则 $A(S) = false$。自动机由五个部分组成，$alpha$ 为字符集，$state$ 状态集合，$init$ 初始状态，$end$ 结束状态集合，$trans$ 状态转移函数。

$tarns(s, ch)$ 表示当前状态是 $s$，在读入后字符 $ch$ 后所到达的状态；同时 $tarns(s, str)$ 表示当前状态是 $s$，在读入后字符串 $str$ 后所到达的状态。

如果 $trans(s, ch)$ 这个转移不存在，我们设其为 null，同时 null 只能转移到 null，null 表示不存在的状态。

问题很简单，已知 $n, k, s(l)$，$\forall i \in N^+, i \leq n$，求 $\sum\limits_{j = 1}^i (\sum\limits_{l = j}^i s(l))^k) \text{ mod } 1000000007$。
即求:

共 $n$ 个数，其中 $\sum\limits_{i = a}^b f(i)$ 表示 $f(a) + \cdots + f(b)$ 的和。

从前，有一只懒猫叫 $CJB$。每个小时，这只猫要么在睡觉，要么在吃东西，但不能一边睡觉一边吃东西，并且这只猫会在一整个小时干同一件事情。

对于接下来的 $n$ 个小时，$CJB$ 知道他在哪 $n$ 个小时睡觉和吃东西的快乐值。

为了健康地生活，在任意的连续 $k$ 个整小时内，$CJB$ 要有至少 $m_s$ 小时睡觉，至少 $m_e$ 个小时在吃东西。也就是说一共有 $n - k + 1$ 段的 $k$ 小时需要满足上述条件。

你的任务是告诉 $CJB$ 他接下来 $n$ 个小时能获得的最大快乐值是多少。

将 $n_1$ 个 $A$，$n_2$ 个 $B$，$n_3$ 个 $C$，$n_4$ 个 $D$ 排成一个序列。求问有多少种排列方案使得排成的序列任意相邻的两个字母不同。

晓华所在的工作组正在编写一套高精度科学计算的软件，一些简单的部分如高精度加减法、乘除法早已写完了，现在就剩下晓华所负责的部分：实数的高精度开m次根。因为一个有理数开根之后可能得到一个无理数，所以这项工作是有较大难度的。现在要做的只是这项工作的第一步：只对自然数进行开整数次根，求出它的一个非负根，并且不考虑结果的小数部分，只要求把结果截断取整即可。程序需要根据给定的输入，包括需要开根的次数，以及被开根的整数；计算出它的非负根取整后的结果。

兔子们在玩 $k$ 个串的游戏。首先，它们拿出了一个长度为 $n$ 的数字序列，选出其中的一
个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。

兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第
$k$ 大的和是多少。

兔子们在玩两个串的游戏。给定两个字符串 $S$ 和 $T$，兔子们想知道 $T$ 在 $S$ 中出现了几次，
分别在哪些位置出现。注意 $T$ 中可能有“?”字符，这个字符可以匹配任何字符。

兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合S，然后它们定义一个字
符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合S中某个字符串的前缀。
比如对于字符串集合 {“abc”,”bca”}，字符串 “abb”，”abab”是“好”的（”abb”=”ab”+”b”,abab=”ab”+”ab”），而字符串“bc”不是“好”的。

兔子们想知道，一共有多少不同的“好”的字符串。

一次舞会有 $n$ 个男孩和 $n$ 个女孩。每首曲子开始时，所有男孩和女孩恰好配成 $n$ 对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和 $k$ 个不喜欢的女孩跳舞，而每个女孩也最多只愿意和 $k$ 个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。

有上下界的网络流。
$(u, v)$ 为一条边，$s$ 为源，$t$ 为汇，$S$ 为超级源，$T$ 为超级汇，$d$ 记录下界和。

数论函数：定义域为正整数的函数。

积性函数

定义

积性函数：对于任意两个互质的正整数 $a,b$ ，均满足 $f(ab)=f(a)f(b)$ 的函数 $f$

完全积性函数：对于所有正整数 $a,b$ ，均满足 $f (ab) = f (a) f (b)$ 的函数 $f$

定义逐点加法： $(f + g)(x) = f(x) + g(x)$，$(f \cdot g)(x) = f(x)g(x)$

在进行算法设计时，我们常用的两种线性数据结构是数组和链表。它们各有优缺点。数组特点是元素在内存中紧挨着存储，因而优点是定位快 $O(1)$，缺点是插入删除慢 $O(n)$；而链表则不同，它通过指针将不同位置的元素链接起来，因而优缺点与数组正好相反：定位慢 $O(n)$，插入删除快 $O(1)$。而块状链表，它将数组和链表的优点结合来，各种操作的时间复杂度均为 $O(\sqrt n)$。