这里显然IQ和难度是独立的，他们共同决定成绩的高低，于是成绩是一个collider,而不同成绩会导致不同排名，所以排名是成绩的子代。现在如果我们已经知道一个人的成绩是多少，那么神奇的事情发生了，如果我们知道一个人IQ很低，但成绩很高，那么我们可以推断出难度肯定很低；同理我们知道成绩很高，但难度很大，那么可以推断出IQ很高。原本IQ和难度两个独立的变量在成绩的条件下变得不独立的。

同理，因为ABCD等级是由不同成绩划分出来的，也包含了成绩的信息，所以我们知道一个人的等级同样可以推断出一个人的IQ和难度。因此当条件集是collider的时候，会反而使得两个独立的变量变得不独立。这就是我们判断条件独立性的时候要小心的地方。

概念

机器学习包括以下三个要素，也是一个学习器必须具备的

• 算法：

  • 线性方法：$f(x,\theta)=w^Tx+b$，比如SVM​
  • 非线性方法：$f(x,\theta)=w^T\phi(x)+b$,比如神经网络

• 学习准则：一般我们选择最小化期望风险
  $$
  \mathcal R(f)=\mathbb E_{(x,y)\sim p(x,y)}[\mathcal L(f(x),y)]
  $$

• 优化方法：比如梯度下降

对于一个好的学习器，其泛化能力比较好，意味着模型能适应不仅仅是训练样本更能很好的适用于新样本；

一般抽样出来的独立同分布的训练样本越多越有可能学习出一个泛化能力强的模型；

基本流程

1. 数据采集

   所有的机器学习算法都是数据贪婪的，任何一个算法都可以通过增加数据来达到更好的结果，因此第一步数据采集也是最基础、最重要的一步。

   采集方式：爬虫，公开数据集，数据库；

2. 数据预处理

   即便数据都在手上，但是因为人为、软件、业务导致的异常数据还是比较多的，比如性别数据的缺失、年龄数据的异常，异常数据对模型是有影响的，因此通常需要进行预处理 。

   预处理问题类型：缺失处理，异常处理（绝对异常，统计异常，上下文异常）

3. 特征工程

   特征工程指的是把原始数据转变为模型的训练数据的过程，它的目的就是获取更好的训练数据特征，使得机器学习模型逼近上限。一般来讲，特征工程包含特征选择、特征提取和特征构建。

   • 特征选择:剔除不相关或者冗余的特征，减少有效特征的个数，减少模型训练的时间，提高模型的精确度。

   • 特征自身的取值分布：主要通过方差过滤法，比如性别特征，1000个数据，999个是男的，1个是女的，这种特征由于自身过于偏斜，因此是无法对结果起到足够的帮助。

   • 特征与目标的相关性：可以通过皮尔逊系数、信息熵增益等来判断，思路是如果一个特征与目标的变化是高度一致的，那么它对于预测目标就是具有很大指导意义的。

   • 特征构建：指的是从原始数据中人工的构建新的特征。需要人工的创建它们。这需要花大量的时间去研究真实的数据样本，思考问题的潜在形式和数据结构，同时能够更好地应用到预测模型中。

   • 特征组合：例如组合日期、时间两个特征，构建是否为上班时间(工作日的工作时间为1，其他为0)特征，特征组合的目的通常是为了获得更具有表达力、信息量的新特征。

   • 特征拆分：将业务上复杂的特征拆分开，比如将登陆特征，拆分为多个维度的登陆次数统计特征，拆分为多个的好处一个是从多个维度表达信息，另一个多个特征可以进行更多的组合。

4. 模型的构建与调优

   将原始数据映射到特征空间之后，得到比较合理的输入。下一步就是构建合适的预测模型在数据上训练得到对应输入的输出。

   模型选择的一般方法：

   首先我们要对处理好的数据进行分析，判断训练数据有没有类标，若是有类标则应该考虑监督学习的模型，否则可以划分为非监督学习问题。其次分析问题的类型是属于分类问题还是回归问题，当我们确定好问题的类型之后再去选择具体的模型。在模型的实际选择时，通常会考虑尝试不同的模型对数据进行训练，然后比较输出的结果，选择最佳的那个。此外还可以尝试多模型融合，来提高效果。选好模型后是调优问题，可以采用交差验证，观察损失曲线，测试结果曲线等分析原因，调节参数：优化器、学习率、batchsize等。

5. 模型的评价

   模型选择是在某个模型类中选择最好的模型，而模型评价对这个最好的模型进行评价。模型评价阶段不做参数调整而是客观地评价模型的预测能力。

什么是人工智能

AI有四种途径值得我们关注：

1. 像人一样行动

   这样的AI应该具有以下能力，以通过图灵测试，以下也是AI应用最广泛的地方：

   • 自然语言处理
   • 知识表示
   • 自动推理
   • 机器学习
   • 计算机视觉
   • 机器人学

2. 像人一样思考

   领会人脑地思维过程，有三种途径：内省，心理实验和脑成像，只有具备人脑地精确理论，才有可能表示成计算机程序；

3. 合理地思考

   对于逻辑主义希望通过逻辑表示描述任何可解地问题，但是有两个阻碍：如何获得非形式的知识用逻辑表示法描述出来，如何在有限的资源解决困难的问题；

4. 合理地行动

   一个合理Agent希望实现最佳的结果，或者在不确定的环境中实现最佳期望结果；

对于现在处于人工智能发展的新阶段，逐渐从决策型AI过渡到生成式AIGC；

交叉学科

1. 哲学
2. 数学
3. 经济学
4. 神经科学
5. 心理学
6. 计算机工程
7. 控制论
8. 语言学

人工智能带来的问题

1. 准确性问题：如何避免AI一本正经地胡说八道？
2. 版权问题：对于模型按照prompt训练出来的作品，版权归属原作者吗，还是prompt创作者？
3. 伦理问题：AI生成一些性别种族歧视的回答，如何处理？

人工智能的历史

总的来说，分为三次浪潮：

1. 1943-1955孕育期，1956诞生期
2. 1952-1969第一次浪潮（推理的发展）：数学定理证明和通用问题求解器GPS出现，prolog出现，产生式系统出现，神经网络和感知机收敛定理发展，符号主义盛行，联结主义出现；
3. 1966-1973现实困难：神经网络大规模学习被否定，感知机无法解决非线性问题；
4. 1969-1980第二次浪潮（知识的发展）：知识工程和专家系统诞生，神经网络中的反向传播提出；
5. 1980-1987反思：日本五代机和Stanford只是百科全书项目失败。人工智能的冬天来临；
6. 1993后第三次浪潮（学习的发展）：统计模型和深度学习获得成功；

现在认为AI领域科学的方法应该是：机器学习不应该和信息论分离，不确定推理不应该和随机模型分离，搜索不应该和经典的优化和控制分离，自动推理不应该和形式化方法和静态分析分离

Search Heuristics

启发式函数$h(n)$度量当前状态到目标状态的代价估计值，以利用问题的额外信息；

对于不同的问题，采取的启发式函数也不一样，常见的启发式函数有：Manhattan距离，Euclidean距离；

称一个启发式函数是Admissible的（可采纳性），如果这个Heuristics不会过高估计当前状态到目标状态的实际代价；

称一个启发式函数是consistent的（一致性），如果对于当前结点$n$,下一步结点$n’$,和目标结点$x$,有如下三角不等式成立：
$$
h(n)\le c(n,n’,x)+h(n’)
$$
结点$n$的预估代价不会超过每个结点$n$通过某一行动到达$n’$的单步代价与结点$n’$的预估代价和；

一致的启发函数一定是可采纳的；

Greedy Best-first Search

对于GBS来说试图拓展距离目标看起来最近的结点，也就是只利用启发信息,$f(n)=h(n)$

我们从四个方面考察GBS的性能：

• 完备性：即使在有限状态空间中，GBS也是不完备的；
• 最优性：往往也不能达到全局最优解；
• 时间复杂度：$O(b^m)$;
• 空间复杂度：$O(b^m)$;

A* Search

对于A*S来说，采用的代价函数具有如下形式：
$$
f(n)=g(n)+h(n)
$$
其中，$g(n)$表示开始结点到当前结点的实际代价，$h(n)$表示当前结点到目标结点的预估最小代价；

A*S试图拓展使得$f(n)$最小的结点$n$​,下从四个方面考察Astar算法的性能：

• 完备性：A*算法是完备的；

• 最优性：若$h(n)$可采纳，那么树搜索版本具有最优性，若$h(n)$一致，则图搜索版本具有最优性;只需注意到当A*选择结点$n$时，就已经找到了$n$的最优路径；

• 时间复杂度：在所有启发式算法中最优的也是效率最优的；

• 空间复杂度：内存保留已生成的结点，因此对于大规模问题在计算完成前往往就耗尽内存

IDA* Search

类似IDS，采用的截断值不是搜索深度而是$f$代价，但是$f$代价是一个实数，将面临和UCS一样的问题；

相对于A*，确实减少了内存需求；

RBFS

MA*

SMA*

CSP问题

对于CSP问题的形式化描述如下:

• 变量$X={X_1,X_2,\cdots, X_n}$
• 值域$D={D_1,D_2,\cdots, D_n}$:每个变量都有自己的值域；
• 约束集$C$描述变量的取值:有一个变量元组和一个显式的关系函数式描述，例如$<(X_1,X_2),X_1\neq X_2>$
• 状态有部分或者全部变量的赋值来描述：${X_1=x_1,\cdots,X_n=x_n}$
  • 一个合法的赋值不违反任何约束条件；
  • 一个完整的赋值意味着对每个变量都有赋值；
• CSP问题的解式全体合法的，完整的赋值的状态

地图着色问题

四色定理就是一类地图着色问题，也是经典的CSP问题：每一个地图（三连通的简单平面图）都是四面可染色的，也即对任意三正则地图$G$均有$\chi’(G)=3$;

对于Australian Map，CSP形式化如下：

• $X={WA,NT,Q,NSW,V,SA,T}$
• $D_i={red,green,blue}$
• $C={SA\neq WA,SA\neq NT,…, NSW\neq V}$
• 一个可行的解为${WA=red, NT=green, Q=red, NSW=green,V=red,SA=blu,T=red}$

Varieties of CSPs

对于CSP问题，可以根据变量类型和值域类型进行分类：

1. 离散变量

   • 有限值域：size $d$ means $O(d^n)$ for complete assignment

     著名的有SAT问题，这是个NPC问题；

   • 无限值域：例如Job scheduling

2. 连续变量

   • 例如：start/end times for hubble telescope observations

Backtracking Search

类似于DFS，回溯搜素算法式解决CSP问题的基础的无信息算法，可以描述如下：

1. One variable at a time：因为CSP问题都是可交换的，就像[WA = red then NT = green] same as [NT = green then WA = red]，因此在每一步只需要考虑一个变量；
2. Check constraints as you go：固定下一个变量之前，检查约束条件，使得已固定的变量不会相互冲突；

以下是Australian Map的一棵搜索树：

以下是算法伪代码：

简单来说，Backtracking = DFS + variable-ordering + fail-on-violation；

Forward Checking

Filtering

Ordering

基础概念

一个好的AI应该做到以下两点：

• think/behavior rationally
• maximize your expected utility

也就是一个理性的Agent对每一个可能的感知序列，根据已知的感知序列提供的证据和Agent具有的先验知识，理性Agent应该选择能使其性能度量最大化的行动;

那么如何设计一个合理的AI呢？PEAS描述这样的任务环境；

1. 性能度量performance measuere
2. 环境environment
3. 执行器actuator
4. 传感器sensor

一个理性的Agent不一定要做到全知，而且也很难做到，一个合理Agent基于已有感知序列进行行动，为了实现最大化期望性能，必须要做一些必要的信息收集，在位置的环境中探查；

如果一个Agent依赖于设计员的先验知识而不能子集的感知信息，则称Agent缺乏自主性，一个合理Agent应该是自主的，Agent应该学习；

但是在Agent诞生初期很难做到完全自主，当Agent经验较少时，其行为往往是随机的，那么设计者应该提供Agent一些先验知识和学习能力，当得到环境的充足经验后，理性Agent才能独立出先验知识进行有效的行动；

任务环境分类

在实践中我们经常能看到如下环境：

• 完全可观察&部分可观察
• 单Agent&多Agent
• 确定Agent&随机Agent
• 片段式&延续式
• 静态&动态
• 离散&连续
• 已知&未知

举个例子来说，自动驾驶就是要处理一个部分可观察的，多Agent，随机的，连续的，动态的，连续的和未知的环境，这每个方面都很难困难；

Simple-Reflect Agent

对于一个简单反射Agent，可以基于当前的感知选择行动，不关注感知历史，比如说每一步决策都是一个MDP，就像建立简单反射一样；

但是简单反射Agent的智能相当有限，可能会不可避免地陷入无限循环；

Reflect-Agent

对于一个反射性智能体，也就是基于模型的反射Agent,比如它认为状态的改变具有Markov性,为了处理部分可观测的环境，可以让Agent跟踪记录看不到的那部分世界，根据感知历史维持内部状态；

如何更新Agent的内部状态？加入两种知识，统称为世界模型：

• 世界如何独立于Agent发展
• Agent如何影响世界

对于一个当下执行一个动作将导致某种后果，作为先验知识输入到一个Reflect Agent，有如下特征：

• Choose action based on current percept (and maybe memory)
• May have memory or a model of the world’s current state
  • If … now, then …
• Do not consider the future consequences of their actions
• Consider how the world IS now

Planning-Agent

对于一个基于目标的Agent，也许Agent需要一条漫长的行动序列来找到目标途径，这时搜索和规划就是好的方法，特征如下：

• Ask “what if”
• Decisions based on (hypothesized) consequences of actions
• Must have a model of how the world evolves in response to actions
• Must formulate a goal (test)
• Consider how the world WOULD BE

一个基于模型和目标的Agent，要记录世界的状态，也要记录到达的目标集合，选择能达到最终目标的方向行动，如下图；

也有几个改进的版本：

1. Optimal Planning：最小化代价去实现目标；
2. Complete Planning: 找到全局最优解；
3. Replanning：每次规划距离当前最近的点，采用启发式的方法；

基于效用的Agent

Agent的效用就是性能度量的内在化，基于效用的Agent试图最大化它期望的快乐，从而做出理性的决策；

• 多目标冲突时，部分目标可达到时，效用函数可以进行适当的折中；
• 无目标有把握达到时，效用函数可以对依据目标的重要性对成功进行似然加权；

学习Agent

人工智能最需要的就是需要一个在初始未知的环境中运转并逐渐提升的Agent，一个学习Agent似乎能做到这一切，它被分为四个概念组件：

1. 评判元件Critic：告诉学习元件Agent的运转情况，进行反馈；
2. 学习元件Learning Element：负责Agent的改进提高，制定更好的规则；
3. 问题产生器Problem generator：建议探索性的活动；
4. 性能元件Performance element：负责选择外部行动，发生状态的转移和世界的改变；

Adversarial Search

对抗搜索也称为博弈搜索：在一个竞争环境中，两个或两个以上的Agents之间通过竞争实现相反的利益，一方最大化这个利益，另外一方最小化这个利益。

Games

对于人工智能方向的博弈，往往有以下分类：

• Deterministic (确定性的)&stochastic (随机性的)?

• One, two, &more players?

• Zero sum?（零和游戏：对一方有利的东西将对另一方同等程度有害，不存在“双赢”结果）

• Perfect information (states完全可被观察)?

我们通常用以下形式化描述博弈：

• States: 状态空间$S$，初始状态为$s_0$；
• Players:行动玩家集合$P$；
• Actions: 某状态下的合法行动集合$A$；
• Transition Function（Result）: 转移模型$S \times A\to S$
• Terminal Test:终止测试，判断game是否结束；
• Terminal Utilities: 效用函数,描述游戏者$p$在终止状态$s$下的数值，$S\times P \to \mathbb R$， 在零和博弈中，玩家总收益 之和一样；
• Policy：玩家采取的策略$S\to A$

其中$s_0$,Actions, Result定义这个游戏的博弈树：结点是状态，边是此时合法的行动，对于双人博弈来说，奇数层MAX希望效用值最大化，偶数层MIN希望效用值最小化；

给定一棵博弈树，最优策略可以通过检查每个结点的极小极大值来确定，终止状态的极小极大只就是自身的效用值；

对于给定的选择，MAX希望移动到到达极大值的状态，MIN希望移动到极小值的状态；
$$
\mathsf{MINIMAX}(s)=\begin{cases}
\mathsf {Utility}(s)&s为终止状态\
\max_{a\in A}\mathsf{MINIMAX}(\mathsf{Result}(s,a))&s为\mathsf{MAX}结点\
\min_{a\in A}\mathsf{MINIMAX}(\mathsf{Resilt}(s,a))&s为\mathsf{MIN}结点
\end{cases}
$$

Minimax Search

对于简单的博弈问题，可以生成整棵博弈树，找到必胜策略；对于复杂的博弈问题，不可能生成整个搜索树；

一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，并利用代价函数$f(n)$对叶节点进行估值；

对于一棵状态搜索树，玩家交替行棋，已知叶子结点（终止状态）的效用值，求每个结点的Minimax值，也就是best achievable utility；

Minimax就是这样的一个递归算法，一直向下进行到叶节点然后随着递归的展开通过搜索树倒推极小化极大值；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def max-value(state):
    initialize v = -∞
    for each successor of state:
    	v = max(v, value(successor))
    return v
    
def min-value(state):
	initialize v = +∞
	for each successor of state:
		v = min(v, value(successor))
	return v
	
def value(state):
	if the state is a terminal state: 
		return the state’s utility
	if the next agent is MAX: 
		return max-value(state)
	if the next agent is MIN: 
		return min-value(state)

对于上面举例的两层博弈树，max在根节点的最佳移动是$a_1$，因为它指向值最高的状态;而min的最佳响应是$b1$，因为它指向值最低的状态。

$\alpha-\beta$ Pruning

上述的递归程序时间开销是指数级的，完全不使用，我们考虑一个能得到相同结果，剪去不影响结果的搜索分支的剪枝方式；

注意到Minimax Search是一种深度优先的搜索，因此只需要考虑书上某一单一路径上的结点，对于每一个结点，维护两个参数$\alpha,\beta$:

• $\alpha$：目前未知路径上发现的MAX的最佳选择；
• $\beta$:目前为止的路径上发现MIN的最佳选择；

通过维护这两个参数，我们可以省去一些结点的Minimax值计算;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def max-value(state, α, β):
	initialize v = -∞
	for each successor of state:
		v = max(v, value(successor, α, β))
		if v ≥ β 
			return v
		α = max(α, v)
	return v
	
def min-value(state , α, β):
	initialize v = +∞
	for each successor of state:
		v = min(v, value(successor, α, β))
		if v ≤ α 
			return v
		β = min(β, v)
	return v
	
def value(state):
	if the state is a terminal state: 
		return the state’s utility
	if the next agent is MAX: 
		return max-value(state, -∞, +∞)
	if the next agent is MIN: 
		return min-value(state, -∞, +∞)

以下是一个较为复杂的样例：

可以看到，经过剪枝，原本需要访问26个结点的搜索树，现在只需要访问17个结点就得到了根的Minimax值，该技术能有效减少访问搜索树中的结点个数；

行棋排序

$\alpha-\beta$剪枝算法的效率很大程度上取决于检查后继状态的顺序，但是对于状态做出排序事实上是困难的，假设后继状态检查采取的是随机顺序，检查的总结点树大约是$O(b^{\frac{3m}{4}})$;

对重复状态的搜索可能会导致搜索代价的指数级增长，不同的行棋顺序可能会导致相同的结果，因此需要将第一次遇到的棋局以及评估值用Hash表存储起来，一般称为换位表；

如果评估的速度过快，那么换位表就不太可能保存所有评估了，也许保留一些有价值的结点可能是比较好的方案；

不完美的实时决策

由于下棋的时间有限，所以Agent应该尽早截断搜索,将启发式评估函数值$h(s)$近似为终端结点的Minimax值，假设$d$为截断搜索的最大深度，截断测试表示为CUTOFF(s,d)转移方程应变为：
$$
h(s)=\begin{cases}
\mathsf {Eval}(s)& \mathsf{CUTOFF}(s,d)=True\
\max_{a\in A}h(\mathsf{Result}(s,a))&s为\mathsf{MAX}结点\
\min_{a\in A}h(\mathsf{Resilt}(s,a))&s为\mathsf{MIN}结点
\end{cases}
$$
为了避免Agent出昏招，评估函数对终止状态的排序要和真正的效用函数排序结果一样；

评估函数的计算开销不能太大，而且应该和取胜几率密切相关；

假如说对于国际象棋这种状态完全可观察的博弈问题来说，可以由子力价值，关键位置，王的安全性等等，这往往是设计者的先验知识；

我们从不同的角度评估棋局，最终可得到一个加权平均的方案作为评估函数值如下：
$$
Eval(s)=\sum_{i=1}^{n}\omega_i f_i(s)
$$
对于更复杂的博弈问题，人们往往很难总结经验，也许机器学习的技术将更有利于确定评估函数的权值，比如一个象值三个兵；

截断搜索

向前剪枝

查表

N-Queues Puzzle

对于N皇后问题来说，可以形式化为一个CSP问题：

• $X={X_{ij}}_{n\times n}$

• $D_{ij}={0,1}$

• $$
  C=\begin{cases}
  \forall i,j,k:(X_{ij},X_{ik})\in{(0,0),(0,1),(1,0)}\
  \forall i,j,k:(X_{ij},X_{kj})\in{(0,0),(0,1),(1,0)}\
  \forall i,j,k:(X_{ij},X_{i+k,j+k})\in{(0,0),(0,1),(1,0)}\
  \forall i,j,k:(X_{ij},X_{i+k,j-k})\in{(0,0),(0,1),(1,0)}\
  \sum_{i,j}X_{ij}=N
  \end{cases}
  $$

这个描述有些复杂了，我们给出一个等价描述：

• $X={Q_k}_{k=1}^n$;

• $D_k={1,2,\cdots,N}$;

• $$
  \forall i,j, non-threatening(Q_i,Q_j)\(Q_1,Q_2)\in{(1,3),(1,4),\ldots}
  $$

静态区间最值动态查询

Preface

对于两数比较大小算法[](int a, int b){return a>b?a:b;},时间复杂度为$O(1)$;

对于数组查询最大数，可以用如下归并算法:

1
2
3
4
5
6

int Max(int* a, int l, int r) {
	if(r==l) return a[l];
	int m = l + r >> 1;
	return max(Max(a, l, m), Max(a, m+1, r));
}
int max_val = Max(a, 0, n) 

时间复杂度为$O(logN)$;

Content

对于静态区间最值动态查询（RMQ）的描述如下：

给定一个长度为 $N$ 的数列，和 $M $次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 $N,M$，分别表示数列的长度和询问的个数。

第二行包含 $N$ 个整数（记为 $a_i$），依次表示数列的第 $i$ 项。

接下来 $M$ 行，每行包含两个整数 $l_i,r_i$，表示查询的区间为 $[l_i,r_i]$。

输出格式

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

样例输入

1
2
3
4
5
6
7
8
9
10

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

样例输出

1
2
3
4
5
6
7
8

9
9
7
7
9
8
7
9

对于常规的在线处理查询，时间复杂度为$O(MlogN)$，对于$M$很大时无法接受；

现在引入跳表($st$​表)数据结构如下：

给定数组$a[1…n]$,查询区间$(a[l],..,a[r])$之间的最（大）值query(l,r);

对于二维数组$dp[i][j]$,表示一个长度为$2^j$的区间$[i, i+2^j-1]$之间的最大值；

那么基于倍增的思想，我们可以写出如下转移式：
$$
dp[i][j]=\max(dp[i][j-1], dp[i+2^{j-1}][j-1])
$$
对于一般的区间$[s,t]$，在维护跳表之后，可以被拆分为两个区间之并：
$$
[l,r]=[l,l+2^s-1]\cup [r-2^s+1,r], s=\lfloor log_2(r-l+1) \rfloor
$$
于是查询可简化为query(l,r)=max(dp[l][s], dp[r-(1<<s)+1][s]);

题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# include <fstream>
# include <iostream>
# include <vector>
using namespace std;

vector<int> Log;
vector<int> a;
vector<vector<int>> dp;

void pre(int n, int m, vector<int> &a, vector<vector<int>> &dp){
    Log.push_back(0);
    Log.push_back(0);
    Log.push_back(1);
    for(int i=3;i<=n;i++) Log.push_back(Log[i>>1]+1);
    dp.resize(n+1, vector<int>(Log[n]+1));
    for(int i=1;i<=n;i++) dp[i][0]=a[i];
    for(int j=1;j<=Log[n];j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp[i][j]=max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l, int r){
    int s = Log[r-l+1];
    return max(dp[l][s], dp[r-(1<<s)+1][s]);
}
int main(){
    #ifdef DEBUG
    std::ifstream input("input.txt");
    std::ofstream output("output.txt");
    if (!input.is_open() || !output.is_open()) {
        cerr << "Failed to open input or output file." << endl;
        return 1;
    }
    std::streambuf* cinBuf = std::cin.rdbuf();
    std::streambuf* coutBuf = std::cout.rdbuf();
    std::cin.rdbuf(input.rdbuf());
    std::cout.rdbuf(output.rdbuf());
    #endif

    int n, m;
    cin>>n>>m;
    a.resize(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    pre(n, m, a, dp);
    while(m--){
        int l,r;
        cin>> l >> r;
        cout<<query(l,r)<<endl;
    }

    #ifdef DEBUG
    std::cin.rdbuf(cinBuf);
    std::cout.rdbuf(coutBuf);
    input.close();
    output.close();
    a.clear();
    dp.clear();
    #endif

    return 0;
}

Remark

嗯被快读卡住了，懒得改了；

事实上区间最值用线段树比较好，但是线段树对动态变化的数组威力更大，这个就是静态的数组；

也不止只有RMQ可以用st表，还有其它的「可重复贡献问题」。例如「区间按位与」、「区间按位或」、「区间 GCD」，ST 表都能高效地解决[^1]。

[^1]: ST 表 - OI Wiki (oi-wiki.org)