两道树状数组

发表于 更新于 分类于 ， ， 本文字数： 4.2k 阅读时长 ≈ 8 分钟

最近又好颓废呀，暑假想写的两道树状数组的题解拖到了今天。

Movie Collection(NWERC 2011)

传送门： Gym - 100729C

Problem

Description

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.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test
case:
• 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.

Output

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
stack.

Sample Input

2
3 3
3 1 1
5 3
4 4 5

Sample Output

2
3 3
3 1 1
5 3
4 4 5

Solution

Idea

这题有些像树状数组求逆序数对个数的思路。自己一开始的想法很接近正解，但是因为没有完全理解求逆序数个数的思想，只有模糊的思路，不会敲，很可惜！

首先，我们用数组来模拟题意，n=5 时一开始的状态为 54321， 如果要看 4，则变为 53214，在后边加一个数字。用一个大小为 n+m 的树状数组来维护前缀和， bit [i] 表示到 i 位置有多少部片子，最初在每个位置都加 1，当我们观看一部时，就在它原来的位置 - 1，在新的位置加 1，更新它的位置即可。见代码。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define MAXN 100010
int bit[MAXN<<1];
int pos[MAXN];
int n, m;

void update(int x, int val)
{
    while(x<(MAXN<<1))
    {
        bit[x] += val;
        x += (x&-x);
    }
}

int query(int x)
{
    int sum = 0;
    while(x)
    {
        sum += bit[x];
        x -= (x&-x);
    }
    return sum;
}

int main()
{
    int T;
    scanf("%d", &T);
    int ans = 0;
    int x;
    while(T--)
    {
        memset(bit, 0, sizeof(bit));
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++)
        {
            update(i, 1);
            pos[i] = n-i+1;
        }

        for(int i=1; i<=m; i++)
        {
            scanf("%d", &x);

            ans = query(i+n-1) - query(pos[x]);
            update(pos[x], -1);
            pos[x] = i+n;
            update(pos[x], 1);
            printf("%d%c", ans, " \n"[i==m]);
        }

    }
    return 0;
}

Note

感觉是极其经典的树状数组的应用，更加理解了求逆序数对的方法。

Bitris(SEERPC 2012)

传送门: [Gym - 101472B]

Problems

Description

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
eliminated.

Input data.

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.

Output data.

The only line in the output should contain one non-negative integer M – the minimal
number of swaps necessary to destroy all cubes.

Sample iutput

4
2 1 4 3 3 1 4 2

Sample output

1

Sample input

3

1 3 2 1 3 2

Sample output

3

Solution

Idea

每进来一个，如果之前出现过这个数字，我们优先让它消除就好。至于要交换多少次，就类似上面一题的思路。

2018.09.21 更

懒惰，不想写了，放过我吧。