526互联

[ABC328C] Consecutive 题解

发布时间 2023-11-19 16:54:50作者: merlinkkk

Hello World

链接

这道题是一个很明显的前缀和，我们把 $sum_i$ 表示为前 $i$ 个字符有多少个有重复，查询的时候就用 $sum_{r-1}-sum_{l-1}$ 就行了。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int sum[300010];
int main()
{
	int n,q;
	cin>>n>>q>>s;
	for(int i=1;i<n;i++)
		s[i]==s[i-1]?sum[i]=sum[i-1]+1:sum[i]=sum[i-1];
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<sum[r]-sum[l]<<endl;
	}
	return 0;
}