Movie Collection(NWERC 2011)
传送门： Gym - 100729C
Mr. K. I. has a very big movie collection. He has organized his collection in a big stack.
Whenever he wants to watch one of the movies, he locates the movie in this stack and removes
it carefully, ensuring that the stack doesn’t fall over. After he finishes watching the movie, he
places it at the top of the stack.
Since the stack of movies is so big, he needs to keep track of the position of each movie.
It is sufficient to know for each movie how many movies are placed above it, since, with this
information, its position in the stack can be calculated. Each movie is identified by a number
printed on the movie box.
Your task is to implement a program which will keep track of the position of each movie.
In particular, each time Mr. K. I. removes a movie box from the stack, your program should
print the number of movies that were placed above it before it was removed.
On the first line a positive integer: the number of test cases, at most 100. After that per test
• one line with two integers n and m (1 ≤ n, m ≤ 100 000): the number of movies in the
stack and the number of locate requests.
• one line with m integers a1, . . . , am (1 ≤ ai ≤ n) representing the identification numbers
of movies that Mr. K. I. wants to watch.
For simplicity, assume the initial stack contains the movies with identification numbers 1, 2, . . . , n
in increasing order, where the movie box with label 1 is the top-most box.
Per test case:
• one line with m integers, where the i-th integer gives the number of movie boxes above
the box with label ai
, immediately before this box is removed from the stack.
Note that after each locate request ai
, the movie box with label ai
is placed at the top of the
3 1 1
4 4 5
3 1 1
4 4 5
首先，我们用数组来模拟题意，n=5 时一开始的状态为 54321， 如果要看 4，则变为 53214，在后边加一个数字。用一个大小为 n+m 的树状数组来维护前缀和， bit [i] 表示到 i 位置有多少部片子，最初在每个位置都加 1，当我们观看一部时，就在它原来的位置 - 1，在新的位置加 1，更新它的位置即可。见代码。
传送门: [Gym - 101472B]
There is a set of 2xN cubes. Each cube has an integer ranging from 1 to N assigned to it, labeling
each of the cube’s sides. Each number is written on exactly two cubes. Cubes are placed one on
top of another, in a pile. If two cubes with the same number stand next to each other, they
annihilate: both cubes disappear, and cubes standing above come down to fill the space.
Your task is to disassemble the pile – eliminate all cubes. You are allowed
to swap any two neighboring cubes. A swap could be done only after all
possible annihilations are done.
For example, if N=4 and cubes are standing as you see on the right then
you need to make one swap. Cubes with label 3 annihilate immediately;
you swap the fourth bottom cube (with label 1) and the fifth bottom cube
(with label 4); afterwards, cubes with labels 4 annihilate, followed by cubes
with labels 1 and labels 2. Other option is to swap third and fourth bottom
cubes (in this case cubes with labels 1 and 4 annihilate at same time,
followed by cubes with label 2), or second and third.
If N=3, and cubes are standing like shown on the right, you need to
perform 3 swaps. One way to solve is to swap fifth and sixth cubes, then
fourth and fifth; cubes with labels 2 annihilate; then swap second and
third; other cubes annihilate simultaneously.
The task is to find the minimal number of swaps, such that all cubes are
The first line in the input file contains the positive integer N,
2<=N<=100000. The second line contains the labels of all cubes, bottom up, split by spaces.
The only line in the output should contain one non-negative integer M – the minimal
number of swaps necessary to destroy all cubes.
2 1 4 3 3 1 4 2
1 3 2 1 3 2