Problem H
Ahoy, Pirates!
Input: Standard
Input
Output: Standard
Output
In the ancient pirate ages, the
There were N pirates and all of the pirates have a unique id from 0 to N-1. The great magician could mutate a bunch of pirates with consecutive id’s to another one.
Suppose there were 100 pirates in the pirate land and all of
them were
The magician was very fast casting the spell. Once, God started to dislike this. God had favor for the Buccaneer pirates and God asked the magician, “Tell me, how many of the pirates of index from 2 to 30 are Buccaneer pirates?”. Now the magician was puzzled as he was only efficient in casting spells, not in counting J
Being clever enough, the magician captured a clever man from
the
Input
The first line of input will contain number of test cases T.
For each test case:
The first part of the description will be of the pirate
land. There could be up to N (1<=N<=1024000) pirates. Each pirate is
either assigned to Buccaneer or Barbary Pirate. Buccaneer pirates are described
by ‘1’ (ONE) and
Now the next part of the input will contain queries. First line of next part has an integer Q describing number of queries. Each subsequence Q (1<=Q<=1000) lines describe each query. Each query has a string F or E or I or S and two integers, a and b denoting indexes. The meaning of the query string are follows:
F a b, means, mutate the pirates from index a to b to Buccaneer Pirates.
E a b, means, mutate the pirates from index a to b to Barbary Pirates.
I a b, means, mutate the pirates from index a to b to inverse pirates.
S a b, means, “God’s query” God is asking a question: “Tell me, how many Buccaneer pirates are there from index a to b?”
(a <= b, 0 <= a < n, 0 <= b < n, index range are inclusive)
Output
For each test print the case number as the sample output suggests. Then for each of “God’s query”, output the query number, colon (:) and a space and the answer to the query as the sample suggest.
Sample Input Output
for Sample Input
2 2 5 10 2 1000 5 F 0 17 I 0 5 S 1 10 E 4 9 S 2 10 3 3 1 4 0 2 0 2 I 0 2 S 0 8 |
Case 1: Q1: 5 Q2: 1 Case 2: Q1: 0 |
Explanation:
Case1:
The pirate land is as follows (N = 18)
101010101010001000
Before God’s first query it was as follows
000000111111111111
Case 2:
The pirate land is as follows (N=9)
111000000
Problemsetter: Istiaque Ahmed
Special Thanks to: Mohammad Mahmudur
Rahman