什么是主席树
主席树：可持久化线段树，特点是每次修改都新建一颗新树，由于单点修改最多影响$\log n$个节点，因此只需要新建一条链，挂在原树上
问题：[COGS 2554][福利]可持久化线段树 RMQ问题的可持久化版本
这是一道板子题，但是此题没有体现主席树的经典应用，代码如下：
阅读全文普通的快速幂
计算$a^b\mod m$，其中$0\leq a,b\leq10^{16}$。
我们可以写出如下的暴力求幂程序，复杂度$O(n)$:
typedef long long ll;
ll pow_mod(ll a,ll b,ll m)
{
ll ans=1;
while(b--)
ans=(ans*a)%m;
return ans;
}
不过注意到对于任意正整数k，我们都可以拆成至多$log k$个二进制下的1,所以我们可以计算出$a^{2^0},a^{2^1},a^{2^2},\cdots$（可以递推出来）,然后再用$\log b$次乘法将其合并起来，复杂度为$O(\log n)$，代码如下：
ll fast_pow_mod(ll a,ll b,ll m)
{
ll ans=1;
while(b)
{
if(b&1)
ans*=a;
a*=a;
b>>=1;
}
return ans;
}
由快速幂魔改的快速乘
由于$a\times b$可能溢出，因此不能直接乘起来再取膜，考虑到一个事实： $$ a^b= \begin{cases}
1 & b=0 \\
\underbrace { a \times \cdots \times a }_b & b \ge 1
\end{cases}
$$
$$
a\times b=
\begin{cases}
0&b=0
\underbrace{a+\cdots+a}_b&b\not=0
\end{cases}
$$
所以我们把上面的代码稍微改一改就好了：
题目
★★☆
输入文件：zootopia.in 输出文件：zootopia.out 简单对比
时间限制：1 s 内存限制：32 MB
【题目描述】
- 物理学要求：为了稳定和美观，半径大的蛋糕必须在放在半径小的蛋糕下面。
- Mr.Big的钦定要求：编号小的蛋糕必须放在编号大的蛋糕下面。
你需要帮他制定一个使多层蛋糕总体积最大的方案。
你只需要计算出最大的总体积即可。 注意：两个半径相同的蛋糕不能放在一起
【输入格式】
第一行一个整数n,
接下来n行,第i+1行两个整数R,H分别表示编号为i的蛋糕的半径和高度。
【输出格式】
只有一行一个整数，为最大总体积,由于出题人懒得写评测插件，你需要精确到小数点后2位
题解
思路
此题乍一看是普通的最长上升/下降子序列，然而$O(n^2)$的做法会挂掉，所以要用$O(nlogn)$的做法
阅读全文