시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB116423544.872%

문제

1차원 세계에는 1차원 체스라는 게임이 존재한다. 1차원 세계에 사는 체스 마스터 무지는 다음 중요한 경기를 위해 기보 분석에 빠져있다.

1차원 체스의 기보는 1부터 10,000까지의 수를 가진 수열 $A$로 나타난다.

또한 두 개의 기보를 비교할 때 처음으로 값이 달라지는 위치가 존재한다면 그 이전 위치 수를 기점이라고 한다. 즉 기보쌍 {$A$, $B$}에 대해 기점은 다음과 같다.

$ 2 \le K$ $\le$ $min$($|A|$,$|B|$) 인 $K$에 대해 $A_{i} = B_{i} $ $(1 \le i < K)$이고 $A_{K}$ $\neq$ $B_{K}$ 이면 두 기보의 기점은 $A_{K-1}$로 정의된다.

기보쌍의 기점이 존재하지 않을 수도 있다.

무지는 $N$ 개의 기보를 가지고 있고 가능한 모든 기보쌍에 대해 특정 수들이 몇 번이나 기점이 되는지 궁금하다. 무지를 도와주자.

입력

입력의 첫 줄에 기보의 개수 $N$과 무지가 궁금한 수의 개수 $Q$ 가 정수로 주어진다. ($ 2 \le N \le 100,000 $, $ 1 \le Q \le 10,000 $)

두 번째 줄부터 $N+1$ 줄까지 각 줄마다 기보의 크기를 나타내는 정수 $S$ 가 주어지고 $A_{1} \; A_{2} \, ... \,A_{S}$ 의 형태로 기보의 값이 정수로 주어진다. ($ 1 \,\le \,S$, $ 1 \le A_{i} \le 10,000 $)

$N+2$줄부터 $N+Q+1$ 줄까지 무지가 궁금한 수들이 각 줄마다 $Q_{i}$ 형태로 주어진다. ($ 1 \le Q_{i} \le 10,000 $, $Q_{i}$ 는 모두 서로 다르다)

전체 기보의 크기 합은 $1,000,000$ 을 넘지 않는다. ($\sum S \le 1,000,000$)

출력

무지가 궁금해하는 수들 $Q$개 각각에 대해, 모든 기보쌍을 비교했을 때 그 수가 몇 번이나 기점이 되는지 $Q$개의 줄에 나눠서 순서대로 출력하자.

예제 입력 1

6 4
3 1 2 3
4 1 2 4 5
4 1 2 4 6
6 2 23 23 3 3 23
6 2 23 23 3 3 23
3 2 23 21
2
3
4
23

예제 출력 1

2
0
1
2

수 2는 기보쌍 {1, 2}와 {1, 3}에 대해 기점이며

수 23은 기보쌍 {4, 6}와 {5, 6}에 대해 기점이다.

수 3은 어떤 기보쌍 {i, j} 에 대해서도 기점이 될 수 없다.

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2021 G번