Zigu Zagu solution codeforces – You have a binary string 𝑎a of length 𝑛n consisting only of digits 00 and 11.
[Solution] Zigu Zagu solution codeforces
You are given 𝑞q queries. In the 𝑖i-th query, you are given two indices 𝑙l and 𝑟r such that 1≤𝑙≤𝑟≤𝑛1≤l≤r≤n.
Let 𝑠=𝑎[𝑙,𝑟]s=a[l,r]. You are allowed to do the following operation on 𝑠s:
- Choose two indices 𝑥x and 𝑦y such that 1≤𝑥≤𝑦≤|𝑠|1≤x≤y≤|s|. Let 𝑡t be the substring 𝑡=𝑠[𝑥,𝑦]t=s[x,y]. Then for all 1≤𝑖≤|𝑡|−11≤i≤|t|−1, the condition 𝑡𝑖≠𝑡𝑖+1ti≠ti+1 has to hold. Note that 𝑥=𝑦x=y is always a valid substring.
- Delete the substring 𝑠[𝑥,𝑦]s[x,y] from 𝑠s.
For each of the 𝑞q queries, find the minimum number of operations needed to make 𝑠s an empty string.
Note that for a string 𝑠s, 𝑠[𝑙,𝑟]s[l,r] denotes the subsegment 𝑠𝑙,𝑠𝑙+1,…,𝑠𝑟sl,sl+1,…,sr.
The first line contains two integers 𝑛n and 𝑞q (1≤𝑛,𝑞≤2⋅1051≤n,q≤2⋅105) — the length of the binary string 𝑎a and the number of queries respectively.
The second line contains a binary string 𝑎a of length 𝑛n (𝑎𝑖∈{0,1}ai∈{0,1}).
Each of the next 𝑞q lines contains two integers 𝑙l and 𝑟r (1≤𝑙≤𝑟≤𝑛1≤l≤r≤n) — representing the substring of each query.
[Solution] Zigu Zagu solution codeforces
Print 𝑞q lines, the 𝑖i-th line representing the minimum number of operations needed for the 𝑖i-th query.
5 3 11011 2 4 1 5 3 5
1 3 2
[Solution] Zigu Zagu solution codeforces
10 3 1001110110 1 10 2 5 5 10
4 2 3
Zigu Zagu solution codeforces
In the first test case,
- The substring is 𝟷𝟶𝟷101, so we can do one operation to make the substring empty.
- The substring is 𝟷𝟷𝟶𝟷𝟷11011, so we can do one operation on 𝑠[2,4]s[2,4] to make 𝟷𝟷11, then use two more operations to make the substring empty.
- The substring is 𝟶𝟷𝟷011, so we can do one operation on 𝑠[1,2]s[1,2] to make 𝟷1, then use one more operation to make the substring empty.