Count Substrings

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 i^{th} query, two integers L_{i} and R_{i} 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 L^{th} to R^{th} 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.
Input
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 spaceseparated 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 i^{th} line of them contains two spaceseparated integers L_{i} and R_{i}.
Output
For each query, print the required answer in a single line.
Constraints and Subtasks
 1 ≤ T ≤ 10^{5}
 1 ≤ K ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 1 ≤ L_{i} ≤ R_{i} ≤ N
 Sum of N over all test cases in one test file does not exceed 10^{5}
 Sum of Q over all test cases in one test file does not exceed 10^{5}
 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.
Example
Input: 1 8 2 3 01110000 1 4 2 4 5 8 Output: 8 5 7
Explanation
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.
Author:  darkshadows 
Tester:  laycurse 
Editorial  https://discuss.codechef.com/problems/STRSUB 
Tags  binarysearch, darkshadows, dynamicprogramming, march15, simple 
Date Added:  18042014 
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, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions