main.cpp (1687B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 // s = s_1, s_2, ..., s_n consisting of only .'s and #'s 11 // m queries 12 // query := l_i, r_i 13 // answer is number of integers l_i <= i <= r_i that s_i = s_{i+1} 14 15 // hmm, can't we just compute a prefix array and then subtract left and right? 16 17 // ...... 18 // m = 4 19 // l_i = 3, r_i = 4 20 // l_i = 2, r_i = 3 21 // l_i = 1, r_i = 6 22 // l_i = 2, r_i = 6 23 24 // ...... 25 26 // inclusive prefix sum: 27 // [1,2,3,4,5,5] 28 29 // l_i = 3, r_i = 4 30 // l_i = 2, r_i = 3 31 // l_i = 1, r_i = 6 32 // l_i = 2, r_i = 6 33 34 // 3,4 35 // p_3 = 3 36 // p_4 = 4 37 // 1 38 39 40 // #..### 41 42 // 011233 43 44 // 1 3 45 46 // 1 - 0 = 1 47 48 // 5 6 49 50 // 1 51 52 // 1 5 53 54 // p_4 - p_1 = 3 - 0 = 2 55 56 // 3 6 57 // 3 4 58 59 // strict inequality on the right so we are interested in the delta between: 60 // where the prefix sum is inclusive 61 // p_{r-1} - p_l 62 63 using namespace std; 64 65 int main() { 66 67 string input; 68 cin >> input; 69 70 vector<int> prefixSumsInc (input.size()+1, 0); 71 72 for(int i = 0; i < input.size()-1; ++i) { 73 if(input[i] == input[i+1]) { 74 if(i > 0) { 75 prefixSumsInc[i+1] = prefixSumsInc[i] + 1; 76 } else { 77 prefixSumsInc[1] = 1; 78 } 79 } else { 80 if(i > 0) { 81 prefixSumsInc[i+1] = prefixSumsInc[i]; 82 } 83 } 84 } 85 prefixSumsInc[(input.size()-1) +1] = prefixSumsInc[input.size()-1]; 86 87 int queryCount; 88 cin >> queryCount; 89 for(int z = 0; z < queryCount; ++z) { 90 int l,r; 91 cin >> l; 92 cin >> r; 93 cout << prefixSumsInc[r-1] - prefixSumsInc[l-1] << endl; 94 } 95 }