Light on or off

Light on or off

时间： 2ms        内存：64M

描述：

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?

输入：

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.

输出：

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.

示例输入：

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

示例输出：

2
3

2

提示：

参考答案：

解锁文章

没有看到答案？微信扫描二维码可免费解锁文章

使用微信扫描二维码打开广告页面后可以立即关闭，再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供，并不代表本站观点！

已经扫描此二维码？点此立即跳转

文章解锁成功，即将自动跳转，点此立即跳转