字串简写(二分)
一眼二分, 枚举起始字符位置,二分搜索满足条件的终止字符的第一个位置,第一个满足则该字符后所有位置相同的字符就都满足了
求res时不用longlong见祖宗 定义变量需谨慎啊!
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int k;
string s;
char a, b;
vector<int> v1, v2;
int main(){
cin >> k >> s >> a >> b;
for(int i = 0; i < s.size(); i ++){
if(s[i] == a) v1.push_back(i);
if(s[i] == b) v2.push_back(i);
}
LL res = 0;
for(int i = 0; i < v1.size(); i ++){
int l = 0, r = v2.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(v2[mid] - v1[i] + 1 >= k) r = mid;
else l = mid + 1;
}
if(v2[l] - v1[i] + 1 < k) continue;
res += v2.size() - l;
}
cout << res << endl;
}