长夜过，最难熬的破晓一定会赴约刚好。
最向往的时光，是一如既往，就好。
自从我打 OI 以来，【集训队互测 2015】未来程序·改 就是我的梦中情题。它需要实现一个 C++ 子集的解释器。当年我的知识水平还远远不足以 A 掉它，只能望题兴叹。
标签： 数据结构
【模板】线段树
题目
题目传送门: 【P3373】【模板】线段树 2 – 洛谷
如题，已知一个数列，你需要进行下面三种操作：
1. 将某区间每一个数乘上 $x$。
2. 将某区间每一个数加上 $x$。
3. 求出某区间每一个数的和。
非旋转 Treap 模板
题目传送门: 洛谷 P3369、LibreOJ #104、BZOJ 3224
我们需要实现一种数据结构，实现以下操作。
1. 插入 $ x $ 数；
2. 删除 $ x $ 数（若有多个相同的数，因只删除一个）；
3. 查询 $ x $ 数的排名（若有多个相同的数，因输出最小的排名）；
4. 查询排名为 $ x $ 的数；
5. 求 $ x $ 的前趋（前趋定义为小于 $ x $，且最大的数）；
6. 求 $ x $ 的后继（后继定义为大于 $ x $，且最小的数）。
栈与队列的基础实现
之前学习栈和队列就不是很系统，这会趁着有时间赶紧补一补。
栈
栈 (stack) 是一种“先入后出”的数据结构。栈的基本结构类似洗盘子，你必须把上面的盘子全部移走，才能够取得下面的盘子。栈的图解如下:
可以看出，栈由两部分组成，数据和栈指针。
在 C++ 中，我们一般通过数组模拟来实现栈。
栈的类型声明如下: