「NOI2007」货币兑换-Splay+斜率优化

小 $Y$ 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:$A$ 纪念券(以下简称 $A$ 券)和 $B$ 纪念券(以下简称 $B$ 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券 和 $B$ 券的价值分别为 $A_K$ 和 $B_K$(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。比例交易法分为两个方面:

(a)卖出金券:顾客提供一个 $[0,100]$ 内的实数 $OP$ 作为卖出比例,其意义为:将 $OP\%$ 的 $A$ 券和 $OP\%$ 的 $B$ 券以当时的价值兑换为人民币;

(b)买入金券:顾客支付 $IP$ 元人民币,交易所将会兑换给用户总价值为 $IP$ 的金券,并且,满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $Rate_K$ ;

注意到,同一天内可以进行多次操作。小 $Y$ 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来 $N$ 天内的 $A$ 券和 $B$ 券的价值以及 $Rate$ 。他还希望能够计算出来,如果开始时拥有 $S$ 元钱,那么 $N$ 天后最多能够获得多少元钱。

Splay学习笔记

伸展树(Splay Tree)是一种二叉查找树,它能在$O(log n)$内完成插入、查找和删除操作。它是由丹尼尔·斯立特(Daniel Sleator)和罗伯特·塔扬(Robert Tarjan)在1985年发明的。其也可以维护区间信息,当作类似线段树的数据结构。

「SCOI2013」多项式的运算-Splay

维护一个动态的关于 $x$的无穷多项式 ,这个多项式初始时对于所有 $i$ 有 $a_i = 0$

$$
f(x)=a_0x^0+a_1x^1+a_2x^2…
$$

操作者可以进行四种操作:

  • mul L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数乘上某个定值 $v$ ;

  • add L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数加上某个定值 $v$ ;

  • mulx L R 表示将 $x^L$ 到 $x^R$ 这些项乘上x变量;

  • query V 求 $f(v)$ 的值。

操作集中在前三种,第四种操作不会出现超过 $10$ 次。

「CQOI2014」排序机械臂-Splay

维护一个序列,第 $i$ 次操作时寻找第i小的数的所在位置 $P_i$,并将 $(P_{i-1},P_{i}]$ 的区间翻转。

如果有相同的数,必须保证排序后它们的相对位置关系与初始时相同。

「NOI2004」郁闷的出纳员-Splay

维护一个数列。
现有四种命令,新加入一个数$k$,把每个数加上$k$,把每个数减去$k$,查询第$k$大的数。如果数列中的任意数小于$min$,将它立即删除。并在最后输出总共删去的数的个数$res$。

如果新加入的数k的初值小于$min$,它将不会被加入数列。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×