UVa 1513 - WinDaLex/Programming GitHub Wiki

from Chapter 3. Data Structures :: Maintaining Interval Data :: Exercises: Beginner

K.I.先生收集了非常多影碟，他把他所有的影碟叠了一叠。在他想看电影的时候，他会从那一叠影碟中找到要看的电影，然后小心翼翼地抽出来。等看完电影后，再把影碟叠到最上面。

因为影碟实在太多了，K.I.先生想要快速地找到每部电影的位置，因此他需要知道每一张影碟的上面到底叠了多少张影碟。现在，有足够的信息可以知道有多少影碟叠在一张影碟上，并且每张影碟都会在盒子上标记一个唯一的编号。

你的任务就是实现一个能够跟踪每张影碟的位置的程序。准确来说，每次K.I.先生从一叠影碟中抽出一张影碟的时候，你的程序都应该输出原先有多少张影碟叠在这张影碟上面。

第一行是一个整数，表示有几组测试数据，不超过100。在每组测试数据中：

• 第一行是两个整数 n 和 m (1 ≤ n , m ≤ 100000)，表示电影的数量和看电影的次数。
• 第二行是m个整数 a₁ , a₂ , ..., a_m (1 ≤ a_i ≤ n )，表示K.I.先生每次看的电影的编号。

为了简单起见，假设影碟一开始是按编号1, 2, ..., n 升序叠放的，编号为1的影碟放在最上面。

对于每组测试数据：

• 在一行里输出m个整数，第i个数表示在看编号为 a_i 的影碟时，在取出它之前，它上面叠了多少张影碟。

别忘了，在看完编号为 a_i 的影碟之后，会将这张影碟叠到最上面。

我们先不考虑题目的初始情况，用 no[i] 表示编号为i的影碟上一次取出之后是第几个放进去的影碟，然后我们利用二叉索引树来完成题目的要求。每次看一张影碟之前，我们先是通过编号，找到影碟上一次放入的顺序，然后从二叉索引树中取出这个数（对应 c[no[i]] -= 1）。看完之后，我们更新它的 no[i] ，再将它放回到二叉索引树中（对应 c[no[i]] += 1）。

这样一来，要知道一张影碟上面叠了多少张影碟，就只需要计算：在取数之前，二叉索引树中有多少个比 no[i] 大的数即可（由于二叉索引树计算有多少个比 no[i] 小的数要更容易，并且我们知道，从头到尾只有 n 张光碟，所以我们的代码可以这样写： ans[i] = n - sum(no[i]) ）。

考虑到题目的初始状态，我们只要一开始将光碟按 n , n - 1, ..., 1的顺序放入二叉索引树中就可以了。

该算法的时间复杂度为 O(n·log(n+m)) 。