Count Substrings That Satisfy K-Constraint II

Given a binary string s and integer k, for each query [l,r] count substrings of s[l..r] whose number of 0's is ≤ k or whose number of 1's is ≤ k. The challenge is to answer up to 1e5 range queries on a string of length up to 1e5, so you need efficient preprocessing (sliding-window/prefix-sum and combinatorial substring counting) to avoid per-query scanning.