Codeforces-162

哭瞎了。

OI 生涯最后一次 CF 做小号然后怒跌。

幸亏没用大号做……否则要会黄啊……

Solution

A

双端队列就可以了。读到一个 l 就在右边插入 i ，否则就在左边插入 i 。

B

直接 dp 就可以了。转移的时候优化一下，记录 g[i] 表示 i 的倍数的最大的 f 值，每次 O(sqrt(n)) 利用 g 来求 f， 再用 f 来更新 g

C

观察数据范围发现 O(nq) 可过，但是 O(nq log n) 也许会超，考虑每次询问重新处理。令 f[i] 表示选取第 i 个球的最大收益，通过枚举最后一个球的颜色来转移。由于只有两种可能性：与上次颜色相同，与上次颜色不同。对于每种颜色维护最大值，线段树查询。

这样会 T 。其实只要维护最大的两个元素就可以了，不用线段树，复杂度降至 O(nq) 。

D

考虑枚举 S 中的每个位置，实时维护 T 中的所有可行位置。

维护两个量， L, R 表示 S 在当前位置时， T 最近、最远在哪里。那么所有可行的位置一定在 [L, R] 内。但并不是所有的位置都是可行的，考虑在当前位置前一位时 [L, R] 内的所有相邻元素，如果相邻两个是 [S[i], S[i - 1]] ，那么 i 这个位置是不能到达的，减去即可。可以证明，其余的位置都可以到达。

E

rng_58 的程序居然这么暴力。哭瞎。

令 f[i] 表示从 i 开始的 LIS 的长度。暴力维护 f 。

插入：由于高度小，只有高度比他小的元素， f 才会受到影响，暴力更新。

删除：由于序号小，只有序号比他小的元素， f 才会受到影响，暴力更新。

situation

首先做了 A ，还是很快的。

然后看了 B 后觉得记录约数是可行的，于是写了。（然后不小心写挂了 T_T）

然后脑残想去 cha 人？于是 Lock 了 B ，然后一个人都没 cha 到。

感觉不行啊，要跪的节奏啊，于是看 CDE 去。

C 瞬间 YY 出 O(nq log n) 的怕 T 不敢写。

一看 E 那不是原题么肿么没人做啊。于是写啊写写啊写好开心～过样例了好开心～交上去 WA 2 了好开心～再仔细一看看错题了好开心～T_T

完了彻底玩脱了。于是赶紧补 C ，YY 出一个 O(nq) 的。结果维护最大的两个值的时候维护错了，交了 4 次才过。

E 题无望，D 题或许还有点可能性。于是继续 YY ，YY 出一个算法了好开心～手跑过不了样例好开心～

继续 YY ，经过各种常数微调似乎可以过样例好开心～3 个样例交上去就 WA 4 好开心～

于是乎小号都会跌……T_T

这大概是除了那次 Bayan 外跌得最惨的一次了……

others

liouzhou_101 稳定发挥 rank 16 怒虐场。

wwwwodddd rank 53 也不错。

cherudim 终于可以不用熬夜了。

大叔只过了 B 。不过遇上了一件奇葩的事：有人用大叔的 ID 交程序 = =|| 。这是肿么做到的……

nonsense

今晚 8 点有 TC 。没小号给我撑着大号要怒跌了。