什么是主席树

主席树:可持久化线段树,特点是每次修改都新建一颗新树,由于单点修改最多影响$\log n$个节点,因此只需要新建一条链,挂在原树上

问题:[COGS 2554][福利]可持久化线段树 RMQ问题的可持久化版本

这是一道板子题,但是此题没有体现主席树的经典应用,代码如下:

阅读全文

题目

★★☆
输入文件:zootopia.in 输出文件:zootopia.out 简单对比

时间限制:1 s 内存限制:32 MB

【题目描述】

  1. 物理学要求:为了稳定和美观,半径大的蛋糕必须在放在半径小的蛋糕下面。
  2. Mr.Big的钦定要求:编号小的蛋糕必须放在编号大的蛋糕下面。

你需要帮他制定一个使多层蛋糕总体积最大的方案。

你只需要计算出最大的总体积即可。 注意:两个半径相同的蛋糕不能放在一起

【输入格式】

第一行一个整数n,

接下来n行,第i+1行两个整数R,H分别表示编号为i的蛋糕的半径和高度。

【输出格式】

只有一行一个整数,为最大总体积,由于出题人懒得写评测插件,你需要精确到小数点后2位

题解

思路

此题乍一看是普通的最长上升/下降子序列,然而$O(n^2)$的做法会挂掉,所以要用$O(nlogn)$的做法

阅读全文