原文oi wiki:树状数组 离散化

数组离散化

离散化步骤

1. 创建原数组的副本，同时记录每个元素出现的位置。
2. 将副本按值从小到大排序，当值相同时，按出现顺序从小到大排序。
3. 将离散化后的数字放回原数组。

原文oi wiki:贪心

贪心策略

1. 序列定义：

   • 序列 $a: a_1, a_2, a_3, \cdots, a_n$
   • 序列 $b: b_1, b_2, b_3, \cdots, b_n$

2. 问题：求 $\sum a_i b_j$（(i, j) 不重复）的最大值

3. 表达式：

   • $max = a_{(1)}b_{(1)} + a_{(2)}b_{(2)} + \cdots + a_{(n)}b_{(n)}$
     （其中 $a_{(i)}$ 是序列 (a) 中第 (i) 大的元素，$b_{(i)}$ 是序列 (b) 中第 (i) 大的元素）

背包DP

原文oi wiki:背包dp

1. 01 背包

每个物品只能获取一次。

模版

01Knapsack

组合数

原文oi wiki:组合数

方法一：数据规模较小时使用动态规划（DP）

当数据规模较小时，可以使用动态规划的方式计算组合数。其核心思路基于组合数的递推公式

$$C_i^j=C_{i-1}^j+C_{i-1}^{j-1}$$

线性、区间、树形 DP

原文oi wiki:树形 DP区间 DP

1. 线性 DP

每个状态只依赖于前一个或前几个状态，且状态转移是线性的（即没有复杂的依赖关系）。通常用于解决序列或数组上的问题。

并查集

原文oi wiki:并查集

基础

介绍

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 顾名思义，并查集支持两种操作： 合并（Union）：合并两个元素所属集合（合并对应的树） 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 路径压缩

原文oi wiki:LIS

简单情形

在最长上升子序列问题中，我们引入两个关键变量 i 和 j。这里，i 表示以其作为结尾的最长上升子序列的长度，而 j 则作为连接点，在构建最长上升子序列的过程中起着重要作用。

需要特别注意的是，dp[mx] 并不一定就是最终答案。在得出所有以不同元素结尾的最长上升子序列长度后，我们需要遍历整个结果数组，才能找出真正的最长上升子序列长度。

搜素专题

原文oi wiki:DFSBFS

1.dfs

子集型:枚举0101,即选或者不选. 排列型:123 132 231 213这样在已知个数的情况下枚举排列顺序

DFS基于栈

原文oi wiki:st表

原理十分简单

基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 $2^i$ 步的话，询问时的复杂度仍旧是 $\Theta(\log n)$，并没有比线段树更优，反而预处理一步还比线段树慢。我们发现$\max(x,x)=x$，也就是说，区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。 如果手动模拟一下，可以发现我们能使用至多两个预处理过的区间来覆盖询问区间，也就是说询问时的时间复杂度可以被降至 $\Theta(1)$，在处理有大量询问的题目时十分有效。

原文oi wiki:string

后缀

后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 S 的从 i 开头的后缀表示为 $Suffix(S, i)$，也就是 $Suffix(S, i) = S[i..|S|-1]$。