很明显是栈了好吧

题目地址

题目大意

给定 本书,序号分别为到，现在执行个操作， 第个操作需要从栈内取出编号为的书，如果该书已经取出，则输出否则将该书从栈内取出，同时取出在栈内比靠上的书，并且输出一共取出了几本书

输入输出格式

输入格式

The first line contains one integer — the number of books in the stack.

The second line contains integers denoting the stack of books.

The third line contains n n integers denoting the steps Vasya is going to perform.

All numbers are distinct, the same goes for .

输出格式

Print integers. The -th of them should be equal to the number of books Vasya moves to his backpack during the -th step.

输入输出样例

#1

1
2
3

3
1 2 3
2 1 3

1

2 0 1 

#2

1
2
3

5
3 1 4 2 5
4 5 1 3 2

1

3 2 0 0 0 

#3

1
2
3

6
6 5 4 3 2 1
6 5 3 4 2 1

1

1 1 2 0 1 1 

解析

本文同步发布于洛谷博客

粗略看了一下 貌似没人和我的解法相同

那就来写一发题解吧

在读入的时候 我们用另一个数组lead[i]来存编号为i的书在**读入的数组book[]**的下标

这样我们在检测读入的书是否被取出时就不用遍历一遍book[]

弹出书本的时候，我们首先看一下这个书本是否被取出

如果是就直接输出0

否则就开始弹出书本

我们用一个变量now = 0记录当前弹出了几个书本，用一个数组vis[i]记录第i本书是否被弹出

在弹出之前，用一个变量orin记录一下还没更新的now

接着在每次弹出的时候更新vis[++now]为真，直到遇到当前要弹出的书本编号

最后orin - now即为答案

代码实现：

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

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <stack>

using std::cin;
using std::cout;
using std::endl;
using std::string;

const int MAXN = 2e5 + 10;

int n;
int book[MAXN];
int lead[MAXN];
bool vis[MAXN];

int now = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", book + i);
        lead[book[i]] = i;
        // 让lead[]作为book[]的索引，查找的时候快一些
    }
    for (int i = 1; i <= n; ++i) {
        int o;
        scanf("%d", &o);
        if (vis[lead[o]]) printf("0 ");
        // 被弹过了，输出0
        else {
            int orin = now;
            while (book[++now] != o) {
                vis[now] = true;
                // 循环更新vis（弹出书本）
            }
            vis[now] = true;
            printf("%d ", now - orin);
        }
    }
    return 0;
}

总感觉自己的代码能被 Hack