【计蒜客T3668 Eye of the Storm】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16519140.html

题目链接

题目

思路

方法一

暴力循环 $[l,r]$ ，判断是否满足题意的数量，复杂度 $O(n^2q)$

方法二

对于上面的方法，显然，其实我们可以只枚举有多少个满足 $S_j=T_2$ ，那么有多少个 $i$ 满足 $S_i=T_1$ 是可以用前缀和预处理后 $O(1)$ 算出来的。复杂度 $O(nq)$

方法三

这种方法是对方法二的一种小优化。

我们在枚举有多少个满足 $S_j=T_2$ 时，我们其实是可以把 $S_i$ 按字母分成26类，在每一类中分别枚举的，这个过程可以用vector辅助实现。

方法四

我们对方法三进行优化。

我们既然已经把 $S_i$ 分类了，而我们要求的是 $[l,r]$ 区间，我们就可以对分类后的 $S_i$ 作个前缀和，然后二分即可。复杂度 $O(q\log n)$

实现上有一些小细节要注意

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define M 30
//#define mo
#define N 200010
int n, m, i, j, k, T; 
int ta, tb, len, l, r, mid, a[N][M], q; 
vector<int>v[M], c[M][M]; 
char s[N], t[N]; 

int count(int m)
{
	int l, r, mid; 
	len=v[tb].size()-1; 
	if(!len) return 0; 
	if(v[tb][1]>m) return 0; 
	l=1; r=len; 
	while(l<r)
	{
		mid=(l+r+1)>>1; 
		if(v[tb][mid]<=m) l=mid; 
		else r=mid-1; 
	}
	return c[tb][ta][l]; 
}

signed main()
{
//	freopen("ridge.in", "r", stdin); 
//	freopen("ridge.out", "w", stdout); 
	n=read(); q=read(); 
	scanf("%s", s+1); 
	for(i=1; i<=26; ++i) 
	{
		v[i].push_back(0); 
		for(j=1; j<=26; ++j) 
			c[i][j].push_back(0); 
	}
	for(i=1; i<=n; ++i) 
	{
		s[i]=s[i]-'a'+1; k=(int)s[i]; 
		for(j=1; j<=26; ++j) 
			a[i][j]=a[i-1][j];  
		a[i][k]++; 
		// for(j=1; j<=26; ++j) 
			// printf("%lld ", a[i][j]); 
		// printf("\n"); 
		v[k].push_back(i); 
		for(j=1; j<=26; ++j) 
			c[k][j].push_back(a[i-1][j]); 
	}
	for(i=1; i<=26; ++i) 
		for(j=1; j<=26; ++j) 
			for(k=1; k<=(int)v[i].size()-1; ++k) 
				c[i][j][k]+=c[i][j][k-1]; 
	while(q--)
	{
		l=read(); r=read(); 
		if(l>r) {
			printf("0\n"); continue; 
		}
		scanf("%s", t+1); 
		ta=t[1]-'a'+1; 
		tb=t[2]-'a'+1; 
		// m=0; k=0; 
		// for(i=1; i<=(int)v[tb].size()-1; ++i) 
			// if(v[tb][i]>=l && v[tb][i]<=r) m+=c[tb][ta][i], ++k; 
		// m-=k*a[l-1][ta]; 
		// for(i=l; i<=r; ++i) 
			// for(j=i+1; j<=r; ++j)
				// if(s[i]==ta && s[j]==tb) ++m; 
		// printf("%lld\n", m); 
		// printf("%lld %lld\n", count(r), count(l-1));  
		printf("%lld\n", count(r)-count(l-1)-(a[r][tb]-a[l-1][tb])*a[l-1][ta]); 
	}
	return 0; 
}