All Tracks Algorithms Graphs Graph Representation Problem

Mancunian And Liverbird Go Bar Hopping
Tag(s):

Algorithms, Easy-Medium, Graph Theory, Implementation

Problem
Editorial
Analytics

It's April Fools' Day 2017 and to celebrate, Mancunian and his arch-enemy Liverbird decide to put aside their differences and go have a drink together.

There are N bars (numbered from 1 to N) located in a straight line. The ith is located at point i on the line. Apart from this, there are N-1 roads, the ith of which connects the ith and i+1th bars. Note that the roads are unidirectional. You are given the initial orientation of each road.

On celebratory occasions such as these, there are a lot of people on the streets. Hence, the police have to take special measures to combat traffic congestion. Periodically, they issue a directive to reverse the direction of all the roads. What this means is that, if there was a road directed from bar numbered i to bar i+1, after the update, it will be directed from i+1 to i.

You are given a set of operations. Each operation can be either an update or a query. Update is the one described above. In each query, you are given the location of the bar the two partyers are located at currently. You have to count the number of bars (including the current location) that are reachable from their current location.

Input:
The first line contains a single integer N denoting the number of bars on the road.
The second line contains N-1 integers denoting the directions of the roads. The ith integer is 1 if the ith road is directed from i to i+1 and 0 if directed from i+1 to i.
The third line contains a single integer Q denoting the number of operations.
Each of the next Q lines is either an update or a query.
An update is given by a single character U.
A query is given in the form of the character Q followed by an integer S denoting the current location of the pair.

Output:
For each query, output a single integer which is the answer to the corresponding query.

Constraints:
1 <= N, Q <= 106
1 <= S <= N

SAMPLE INPUT
4
1 1 0
3
Q 1
U
Q 2
SAMPLE OUTPUT
3
2
Explanation

There are 4 bars on the road, located at 1, 2, 3 and 4 respectively.
The initial configuration of the roads is: 1 -> 2 -> 3 <- 4
You can reach bars 1, 2 and 3 from location 1.
After the update, the new configuration is: 1 <- 2 <- 3 -> 4
Now, you can reach bars 1 and 2 from location 2.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

April Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?