Problem I: Light on or off
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 11 Solved: 1 [ ][ ][ ]Description
There is N lights on the wall of Dreamone’s house from left to right.Initially,some lights on and some lights
off, and we use ‘1’ represented the light on, use ‘0’ represented the light off. As we know, there is a cat in
dremone’s house, and she is very naught. She always change the status continuously from Ath light to Bth
one. (1<=A, B<=N).If the light is on, then the light will be off, If the light is off, then the light will be on.
Actually, she can do it K times like this. Then the cat puts forward another problem: How many lights on
from Cth light to Dth (1<=C, D<=N) one? For example:
When N=4 K=2, and the initial status is assumed as:
1 0 1 1
‘1’ represented on,’0’ represented off.
From the initial status we can get: There is 3 lights on from 1st light to 4th, 2 lights on from 2nd to 4th and so
on. Then we assume the first operation that we change the status from 2nd to 4th, and then the status will be:
1 1 0 0
Then there are 2 lights on from 1st light to 4th one, 1 light on from 2nd to 4th one and so on. Then the second
operation is assumed as from the 1st to 2nd .Then the status will be 0 0 0 0. And there will be no lights on.
Can you get the main idea? Can you help the naught cat?
Input
The first line of input will be a positive integer indicating how many test cases will be included (T) and T
will be less than 10. Each of the next T cases will contain two parts:
The first part: two integer N, K (1<=N<=100000, 1<=K<=100000)
The second part: N numbers (which is ‘0’ or ‘1’) represented the initial status from left to right.
Then third part: K lines. Each line will be X C D (1<=C, D<=N) X is a letter which is either ‘Q’ or ‘C’. If
X=’Q’, you will be output the numbers of lights on from Cth to Dth, and if X=’C’, you will be change the
status of lights as the rules described above.
Output
For each query,(when X=’Q’)，you should output the numbers of lights on. What’s more, you must output a
blank line after you have processed a test case
Sample Input
2
4 3
1 0 1 1
Q 2 4
C 2 3
Q 1 4
4 1
1 0 1 1
Q 2 4
Sample Output
2
3
2