Link Sub: http://www.spoj.com/PTIT/problems/P152SUMI/
Người Gửi: Darkness
- Problem:
Cho một xâu s chỉ gồm các kí tự ‘.’ Và ‘#’, có độ dài n (2 <= n <= 10^5). Cho m truy vấn dạng l[i], r[i] (1 <= l[i] < r[i] <= n). Bạn cần tính kết quả của truy vấn là số lượng các giá trị k (l[i] <= k < r[i]) thỏa mãn s[k] = s[k + 1].
Input
Dòng đầu tiên là xâu s.
Dòng thứ 2 là số nguyên m – số truy vấn.
m dòng tiếp theo, dòng thứ i chứa 2 số nguyên l[i] và r[i].
Output
Gồm m dòng là kết quả của m truy vấn.
Example:
Gồm m dòng là kết quả của m truy vấn.
Input
......
4
3 4
2 3
1 6
2 6
Output:
1
1
5
4
Input
#..###
5
1 3
5 6
1 5
3 6
3 4
Output:
1
1
2
2
0
- Solution:
Tạo một mảng quy hoạch có dạng
xau[i]==xau[i+1]? arr[i+1]=arr[i]+1 : arr[i+1]=arr[i];
với arr[0]=0;
VD: #..###
ta có;
arr[0] = 0;
arr[1] = 0; (#.)
arr[2] = 1; #(..)
arr[3] = 1; #.(.#)
arr[4] = 2; #..(##)
arr[5] = 3; #..#(##)
arr[i+1] = số cặp kí tự giống nhau từ xâu[0 -> i];
-> Với mỗi truy vấn ta có:
Số cặp giống nhau từ l->r = arr[r-1] - arr[l-1];Input
#..###
5
1 3
5 6
1 5
3 6
3 4
Output:
1
1
2
2
0