You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
69 lines
1.7 KiB
69 lines
1.7 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 2e5 + 10;
|
|
|
|
int n, m;
|
|
char S[N];
|
|
vector<int> p[26];
|
|
vector<int> f[26][26];
|
|
int s[N][26];
|
|
|
|
int lower_bound(vector<int> q, int l, int r, int x) {
|
|
while (l < r) {
|
|
int mid = (l + r) >> 1;
|
|
if (q[mid] >= x)
|
|
r = mid;
|
|
else
|
|
l = mid + 1;
|
|
}
|
|
return l;
|
|
}
|
|
int upper_bound(vector<int> q, int l, int r, int x) {
|
|
while (l < r) {
|
|
int mid = (l + r) >> 1;
|
|
if (q[mid] > x)
|
|
r = mid;
|
|
else
|
|
l = mid + 1;
|
|
}
|
|
return l;
|
|
}
|
|
|
|
// 使用手写版本的lower_bound,upper_bound
|
|
int main() {
|
|
freopen("ridge.in", "r", stdin);
|
|
freopen("ridge.out", "w", stdout);
|
|
|
|
cin >> n >> m >> (S + 1);
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
int y = S[i] - 'a';
|
|
for (int x = 0; x < 26; x++) {
|
|
s[i][x] = s[i - 1][x];
|
|
f[x][y].push_back(s[i][x]);
|
|
}
|
|
p[y].push_back(i);
|
|
s[i][y]++;
|
|
}
|
|
for (int i = 0; i < 26; i++)
|
|
for (int j = 0; j < 26; j++)
|
|
for (int k = 1; k < (int)f[i][j].size(); k++)
|
|
f[i][j][k] += f[i][j][k - 1];
|
|
|
|
while (m--) {
|
|
int l, r;
|
|
string t;
|
|
cin >> l >> r >> t;
|
|
|
|
int x = t[0] - 'a', y = t[1] - 'a';
|
|
int ql = lower_bound(p[y], 0, (int)p[y].size(), l);
|
|
int qr = upper_bound(p[y], 0, (int)p[y].size(), r) - 1;
|
|
if (ql > qr) {
|
|
cout << 0 << endl;
|
|
continue;
|
|
}
|
|
int cnt = qr - ql + 1;
|
|
cout << f[x][y][qr] - (ql == 0 ? 0 : f[x][y][ql - 1]) - s[l - 1][x] * cnt << endl;
|
|
}
|
|
return 0;
|
|
} |