APIO '19 P3 - Street Lamps

View as PDF

Submit solution

Points: 35 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

There is a self-driving taxi in Innopolis that drives on a long street. The street consists of n + 1 taxi stops and n segments connecting adjacent stops. There is a street lamp on each segment. The i-th lamp illuminates the segment connecting stop i and i + 1, if the lamp is on. Otherwise, it's dark on the segment.

For the purpose of safety the self-driving taxi can only drive on the segments that are illuminated. In other words, the taxi can drive from the stop a to the stop b (a < b), if the segments between a and a + 1, a + 1 and a + 2, …, b - 1 and b are illuminated.

After breakdowns or repairs the street lamps can turn on or turn off. You are given the initial state of the lamps at the moment 0. After that in the end of hours 1, 2, \dots, q events take place. Exactly one event takes place in the end of each hour, there are two types of events:

  • toggle i — the i-th lamp changes its state: if the lamp was on, it turns off, if the lamp was off, it turns on.
  • query a b — the head of the self-driving taxi department wonders, what is the total time in hours from 0 up to the current time when the taxi was able to drive from stop a to stop b.

Help the head of self-driving taxi department to answer the questions.

Input

The first line contains two integers n and q (1 \le n, q \le 300\,000) — the number of street lamps and number of events.

The second line contains a string s that describes the initial state of the lamps (|s| = n), s_i is 1 if the i-th lamp is on, and s_i is 0 if the i-th lamp is off.

Each of the following q lines describes events. The i-th of these lines describes an event that takes place in the end of the hour i.

  • toggle i (1 \le i \le n) — the i-th lamp changes its state.
  • query a b (1 \le a < b \le n + 1) — calculate the number of hours until the current moment when the taxi was able to drive from stop a to stop b.

At least one of the events is query.

Output

For each query event print a single integer: the answer to the question.

Scoring

Subtask 1 (points: 20)

n \le 100, q \le 100.

Subtask 2 (points: 20)

For all query a b events b - a = 1.

Subtask 3 (points: 20)

For all toggle i events the i-th lamp is turning on.

Subtask 4 (points: 20)

All toggle events happen before all query events.

Subtask 5 (points: 20)

No additional constraint.

Sample Input

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

Sample Output

1
2
0
0
1
2

Explanation

In the sample test:

Hour Lamp states Query Answer
1 11011 query 1 2 1
2 11011 query 1 2 1 and 2
3 11011 query 1 6 None
4 11011 query 3 4 None
5 11011 toggle 3
6 11111 query 3 4 6
7 11111 query 1 6 6 and 7

Comments


  • 1
    maxcruickshanks  commented on Feb. 13, 2022, 1:16 a.m. edited

    Since the original data were weak, 9 more tests cases were added to the last subtask, and the time limit was lowered from 2.5s to 2s.