All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a string S of length N consisting only of 0s and 1s. You are also given an integer K.
You have to answer Q queries. In the ith query, two integers Li and Ri are given. Then you should print the number of substrings of S[L, R] which contain at most K 0s and at most K 1s where S[L, R] denotes the substring from Lth to Rth characters of the string S. In other words, you have to count number of pairs (i, j) of integers such that L ≤ i ≤ j ≤ R such that no character in substring S[i, j] occurs more than K times.
The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains three space-separated integers N, K and Q as described in the problem. The second line contains a string S of length N. Then the next Q lines describe the query, where the ith line of them contains two space-separated integers Li and Ri.
For each query, print the required answer in a single line.
Constraints and Subtasks
- 1 ≤ T ≤ 105
- 1 ≤ K ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- 1 ≤ Li ≤ Ri ≤ N
- Sum of N over all test cases in one test file does not exceed 105
- Sum of Q over all test cases in one test file does not exceed 105
- S consists only of 0s and 1s.
- Sum of N over all test cases in one test file does not exceed 100
- Q = 1
- 1 ≤ K ≤ min(5, N)
- 1 ≤ Q ≤ 10
- Original constraints.
Input: 1 8 2 3 01110000 1 4 2 4 5 8 Output: 8 5 7
Query 1: Consider substring P = S[1, 4] = "0111".
Out of 10 total substrings of P, substrings P[1, 4] and P[2, 4] are not valid because both contain more than two 1s.
Other substrings contains at most two 0s and at most two 1s, thus the answer is 8.
Query 2: Consider substring P = S[2, 4] = "111".
Out of 6 total substrings of P, substrings P[1, 3] is not valid because it contains more than two 1s.
Query 3: Consider substring P = S[5, 8] = "0000".
Out of 10 total substrings of P, substrings P[1, 3], P[1, 4] and P[2, 4] are not valid because all contain more than two 0s.
|Tags||binary-search, darkshadows, dynamic-programming, march15, simple|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.