递推 Codeforces Round #186 (Div. 2) B. Ilya and Queries

 1 /*
 2     递推：用cnt记录前缀值，查询区间时，两个区间相减 
 3 */
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <cstring>
 8 using namespace std;
 9 
10 const int MAXN = 1e5 + 10;
11 const int INF = 0x3f3f3f3f;
12 char s[MAXN];
13 int cnt[MAXN];
14 
15 int main(void)      //Codeforces Round #186 (Div. 2) B. Ilya and Queries
16 {
17     scanf ("%s", s + 1);
18     int len = strlen (s + 1);
19 
20     memset (cnt, 0, sizeof (cnt));
21     for (int i=1; i<len; ++i)
22     {
23         cnt[i] = cnt[i-1] + (s[i] == s[i+1] ? 1 : 0);
24 //        printf ("%d ", cnt[i]);
25     }
26     cnt[len] = cnt[len-1];
27 
28     int m;    scanf ("%d", &m);
29     while (m--)
30     {
31         int l, r;    scanf ("%d%d", &l, &r);
32         printf ("%d
", cnt[r-1] - cnt[l-1]);
33     }
34 
35     return 0;
36 }
编译人生，运行世界！