Level 2. Sereja and Ballons
首先。。。用链表维护每个格子
当某个格子减到0的时候，查询它的 prev[x]，和 succ[x]
记作 a, b。。那么这一轮被删除的区间 (l, r) 满足
l 属于 (a, x]
r 属于 [x, b)
于是就变成了询问一个子矩形点的个数的问题。
。。。这里我们用函数式线段树
查询一个子矩形就是。。。
T[x].Query(b-1, x) - T[a].Query(b-1, x)
Level 2. Music & Lyrics
裸 AC 自动机爆过去了。。。求更好做法。。。
Level 2. Prime Distance On Tree
点分治 + FFT
Level 2. Deleting numbers
主策略。。。
Stage 1. Naive
1. 从后往前逐个删除。
2. 保留出现次数最多的那个。。其他从后往前逐个个删除。。
Stage 2. 树状数组
从后往前逐个删除。但是尝试枚举步长。_L1。取删除个数最多的。。。。
这个算法需要维护删除后的序列。。初期使用的是 STL::vector 。。
但是 erase 毕竟是暴力的。。。所以要想更进一步。。。必须设计数据结构。。。
http://www.codechef.com/viewplaintext/2479887
为了控制常数。。我们排除一些较为复杂的树形结构。。比如各种平衡树。。
果然还是要树状数组。！。。。这样当我们引用元素 i 的时候。。那么它当前真实的位置就是 i – Sum(i)。。
。。这个数据结构。。可以帮助我们确定元素的位置（Rank）。。。但是无法直接告诉我们当前位置为 i 的元素是多少（Pos）
http://www.codechef.com/viewsolution/2520960
Stage 3. 缓存
上述算法的瓶颈在于就在于多次树状数组的查询的操作。。。
。。我们发现在处理与末尾数字相同的时候。。。很多 Rank 的结果是可以重复利用的。。我们对这个结果做 Cache。。
。。。这样一定程度上也可以 O(1) 时间得到 Pos。。。
。。针对这个特性。。。于是我们重新设计算法的框架。。添加两个逻辑层。。。使得我们不是每次都必须要要删除最后一个数字。。
中间一层。。。删除的最后一个数字。。可以是与最后一个数字相同的步长 _M1 以内的任何一个数字。。
最外xxxx。。。xxxxxxxxxxxxxxxxxx。。xxxxxxxxxxxxxxxxxxxx不同xxxxxx _D0 以内的任何一个数字。
最外层的策略使用次数不能太多。。。还得设置一个参数 _C0。。。
http://www.codechef.com/viewsolution/2521453
。。用到的其他优化。。
- 开始就把孤立元素删除。。。（这个优化在 vector 时期效果有限。。但是后期效果越来越明显。。。。
- 在算法的任意时刻。。若出现孤立元素。立即删除。。。（。。这个优化的作用也很明显。。
- . 。。开始和中间时刻。。某个元素只剩 2 个的时候。。也尝试直接清除。。。（。。效果并不明显。。有时不增反减。。。
我们看到其实孤立点并不一定总是直接删除更好。。有的时候保留一些孤立点。。可以令我们中间的过程更具有机动性。。。但是如何利用这种机动性。。却没有什么好的方法。。
。。干脆弃掉算了。。。。
