ABC449C-Comfortable-Distance

大意

给定字符串 $S$ 和整数 $L, R$，求满足 $S_i=S_j$ 且 $L \le j-i \le R$ 的下标对 $(i,j)$ 数量。

思路

暴力枚举 $O(N^2)$ 会超时。利用字符集仅 26 个的特性，将每种字符的下标单独提取。

问题转化为在多个有序数组中，统计差值在 $[L, R]$ 内的数对。对于每个右端点，合法左端点区间随其单调右移，使用双指针维护窗口 $[l, r)$，其中 $l$ 指向首个不小于 $cur-R$ 的位置，$r$ 指向首个大于 $cur-L$ 的位置，累加 $r-l$ 即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pos[500001],L,R,n;
ll idx[27],tmp[1001];
int main(){
	cin>>n>>L>>R;
	string s;
	cin>>s;
	for(ll i=0;i<26;i++)idx[i]=0;
	for(ll i=0;i<n;i++){
		idx[s[i]-'a'+1]++;
	}
	for(ll i=1;i<=26;i++)idx[i]+=idx[i-1];
	for(ll i=0;i<26;i++)pos[idx[i]]=i;
	for(ll i=0;i<n;i++){
		ll c=s[i]-'a';
		pos[idx[c]+tmp[c]]=i;
		tmp[c]++;
	}
	long long t=0;
	for(ll c=0;c<26;c++){
		ll s=idx[c];
		ll e=idx[c+1];
		if(s>=e)continue;
		ll l=s,r=s;
		for(ll j=s;j<e;j++){
			ll cur=pos[j];
			ll minn=cur-R;
			ll maxn=cur-L;
			while(l<e&&pos[l]<minn)l++;
			while(r<e&&pos[r]<=maxn)r++;
			if(r>l)t+=(r-l);
		}
	}
	cout<<t;
}