解法：预处理 + 前后缀分解 / 二分查找

题目每次询问会给出一个区间，只需要找出这个区间内‘#’第一次出现的位置和最后一次出现的位置即可。

下面提供两种做法。

• 前后缀分解 - 时间复杂度 O(N + q):

#include <iostream>
#include <algorithm>
#define endl '\n'

using namespace std;

const int N = 5e5 + 10;

int n, q;
string s;
int l, r;
int pre[N], suf[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> q >> s;
	int p = -1;
	for(int i = 0; i < n; i++) {
		if(s[i] == '.') pre[i + 1] = p;
		else pre[i + 1] = i + 1, p = i + 1;
	}
	p = n + 1;
	for(int i = n - 1; i >= 0; i--) {
		if(s[i] == '.') suf[i + 1] = p;
		else suf[i + 1] = i + 1, p = i + 1;
	}
	
	while(q--) {
		cin >> l >> r;
		if(l > r) swap(l, r);
		cout << max(0, pre[r] - suf[l] + 1) << endl;
	}
	
	return 0;
}

• 二分查找 - 时间复杂度 O(N + q * logN):

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'

using namespace std;

int n, q;
string s;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> q >> s;
	vector<int> v;
	for(int i = 0; i < n; i++) {
		if(s[i] == '#') v.push_back(i + 1);
	}
	while(q--) {
		int l, r; cin >> l >> r;
		if(l > r) swap(l, r);
		int il = lower_bound(v.begin(), v.end(), l) - v.begin();
		int ir = upper_bound(v.begin(), v.end(), r) - v.begin();
		if(il == v.size() || il >= ir) cout << 0 << endl;
		else cout << v[ir - 1] - v[il] + 1 << endl;
	}
	
	return 0;
}