Splay
「NOI2007」货币兑换-Splay+斜率优化
· ✏️ 1924 words · ☕ 4 mins read

小 $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$ 天后最多能够获得多少元钱。


「SCOI2013」多项式的运算-Splay
· ✏️ 1023 words · ☕ 3 mins read

维护一个动态的关于 $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
· ✏️ 1065 words · ☕ 3 mins read

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

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


「NOI2004」郁闷的出纳员-Splay
· ✏️ 1475 words · ☕ 3 mins read

维护一个数列。

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

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