ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8858
サブタスク

COW 순회 1s 1024MB

問題

Farmer John의 농장에는 1…N으로 번호가 매겨진 N (1≤N≤2⋅10^5) 마리의 소가 있으며, 각 소는 자신만의 축사에 삽니다. 각 소 i는 가장 친한 친구 a_i (1≤a_i≤N)가 있습니다. 소는 자기 자신과 가장 친한 친구일 수 있으며, 여러 마리의 소가 같은 소를 가장 친한 친구로 가질 수 있습니다. 소들은 파티를 좋아해서, M (1≤M≤2⋅10^5)일 연속으로 밤마다 파티를 열기로 결정했습니다.

i번째 밤에, 소 c_i는 자신의 축사에서 ti 유형의 파티를 열기로 결정합니다. 여기서 t_i∈"COW"입니다. 이 파티는 소 c_i가 다른 유형의 파티를 열기로 결정할 때까지 향후 모든 밤 동안 계속 유지됩니다.

매일 밤, 각 소는 파티에 가려고 시도합니다. 만약 소가 파티를 열고 있지 않다면, 그 소는 가장 친한 친구의 축사를 확인하고, 그곳에 파티가 없다면 가장 친한 친구가 가는 곳을 따라갑니다 (그 친구 또한 자신의 가장 친한 친구를 따라갈 수도 있습니다). 소가 파티를 전혀 찾지 못해 그날 밤을 포기할 수도 있습니다.

매일 밤마다 C, O, 그리고 W 유형의 파티에 각각 몇 마리의 소가 가게 되는지 계산하세요.


入力

첫 번째 줄에는 소의 수 N이 주어집니다.

두 번째 줄에는 a_1,…,a_N이 주어지며, 여기서 a_i는 i번째 소의 가장 친한 친구입니다.

세 번째 줄에는 밤의 수 M이 주어집니다.

다음 M개의 줄에는 각각 정수 c_i (1≤c_i≤N)와 문자 v_i가 주어지며, 이는 각각 파티를 여는 소와 파티의 종류를 나타냅니다.


出力

M개의 줄을 출력합니다. i번째 줄은 i번째 밤에 C, O, 그리고 W 유형의 파티에 가는 소의 수를 각각 나타내는 공백으로 구분된 3개의 정수로 이루어져 있습니다.


部分問題

番号 点数 条件
#110点

N,M\le 100

#220点

N,M\le 4\ 000

#330点

\{a_i\}는 \{1,…,N\}의 치환(permutation)이다

#440点

추가 제약 조건 없음


例題 

5
2 3 4 5 4
4
2 C
4 C
4 W
2 O
2 0 0
5 0 0
2 0 3
0 2 3

1일 밤, 외양간 2에 C 유형의 파티가 단 하나 열리며, 소 1과 2만 참석합니다.

2일 밤, 외양간 4에 C 유형의 새로운 파티가 열리고, 이제 소 3, 4, 5가 갈 수 있게 됩니다.

3일 밤, 외양간 4의 파티가 W 유형으로 변경되어 소 3, 4, 5에게 영향을 줍니다.

4일 밤, 외양간 2의 파티가 O 유형으로 변경되어 소 1과 2에게 영향을 줍니다.


出典

USACO 2026 First Contest, Gold

ログインしないとコードを書けません。