浅念づ昔夜's Blog

定义

笛卡尔树一是一棵二叉树。对于每个结点，有两个权值 $k,w$。 若只看 $k$，整颗树为二叉查找树；只看 $w$，树为堆。

如图，点在数组中的位置号码为 $k$，元素内数字为 $w$。

分析

用 $\text{map}$ 对数组离散化，防止撑爆树状数组。

从左到右扫一遍数组。$i-1$ 表示左边有 $i$ 个数。显然左边的数与 $a_i$ 构成逆序对的数量为 $i-1$ 减左边比 $a_i$ 小的数的数量。

记得去重。

具有某些优点的随机化算法，适用于最优解问题。

可以根据温度系数决定跳出当前最优解的概率，可以避免陷于局部最优解的情况。

定义最大温度，降温系数，最低温度，当前温度。当前温度初始化为最大温度，每次乘以降温系数，直到低于最低温度。

网络流代码合集

简介

对于一类问题，有两种或多种不同的解法，均无法单独在时限内过题，但在特定的数据范围内优势明显。这时可以设定阈值，对于不同的数据范围，使用不同的算法，令总时间复杂度可以接受。

常见的阈值：$\sqrt{n}$ 等。