COW Traversals
There are N (1≤N≤2⋅105) cows labeled 1…N on Farmer John's farm, where each cow lives in its own barn. Each cow i has a best friend ai (1≤ai≤N). Cows can be best friends with themselves, and multiple cows can have the same best friend. The cows love to party, so they have decided to throw a party for M (1≤M≤2⋅105) consecutive nights.
On night i, cow ci will decide to throw a party of type ti at its barn, where ti∈"COW". This party will exist for all future nights as well, until cow ci decides to throw a party of a different type.
Every night, each cow will attempt to go to a party. If a cow is not hosting a party, they will check their best friend's barn, and if there is no party there, will follow their best friend to wherever they are going (who might also follow their best friend and so on). It is possible that a cow might never find a party and will then give up for the night.
Compute for each night, the number of cows that end up at a party of type C, O, and W respectively.
On night 1, there is only one party of type C at barn 2, which only cows 1 and 2 attend.
On night 2, there is a new party of type C at barn 4, which cows 3, 4, and 5 can now reach.
On night 3, the party at barn 4 is changed to type W, affecting cows 3, 4 and 5.
On night 4, the party at barn 2 is changed to type O, affecting cows 1 and 2.
SCORING:
- Input 2: N,M≤100
- Inputs 3-4: N,M≤4000
- Inputs 5-9: {ai} is a permutation of {1,…,N}
- Inputs 10-21: No additional constraints
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first line contains N, the number of cows.
The second line contains a1,…,aN, where ai is cow i's best friend.
The third line contains M, the number of nights.
The next M lines each contain an integer ci (1≤ci≤N) and a character vi, representing the cow that is throwing the party and the party type respectively.
Output Format
Output M lines, where the ith consists of 3 space-separated integers, the number of cows going to parties of type C, O, and W on the ith night, respectively.