algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }