题目链接：http://codeforces.com/problemset/problem/313/B
题目意思：给出一个只有 "." 和 "#" 组成的序列s，问当给定一个区间 [li,?ri] 时，si?=?si?+?1（".." 或者 "##"）的个数。（li?≤?i?<?ri）
直接做绝对会超时，所以需要离线处理。开一个不比?105小的数组，存储当前得到的最多si?=?si?+?1的数量。感觉上有点像DP的思想......
最后根据给定的 l 和 r，数组下标为 r-1 的数量 - 数组下标为 l-1 的数量即可（数组下标从0开始）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1e5 + 10; 8 int cnt[maxn]; 9 10 int main() 11 { 12 int i, m, l, r, c; 13 string s, tmp; 14 cin >> s; 15 l = s.size(); 16 memset(cnt, 0, sizeof(cnt)); 17 c = 0; 18 for (i = 0; i+1 < l; i++) 19 { 20 tmp = s.substr(i, 2); 21 if (tmp == ".." || tmp == "##") 22 c++; 23 cnt[i+1] = c; 24 } 25 scanf("%d", &m); 26 for (i = 0; i < m; i++) 27 { 28 scanf("%d%d", &l, &r); 29 printf("%d\n", cnt[r-1]-cnt[l-1]); 30 } 31 return 0; 32 } 33
codeforces B. Ilya and Queries 解题报告
原文：http://www.cnblogs.com/windysai/p/3534151.html