莫队
直接莫队就好了。。统计每个字母出现的次数= =
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int ret = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = getchar();
return w ? -ret : ret;
}
inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template <typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template <typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template <typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 200005;
int _, n, q, t, cnt[30], res[N];
char s[N];
struct Query{
int l, r, id, block;
bool operator < (const Query &rhs) const {
return (block ^ rhs.block) ? l < rhs.l : (block & 1) ? r < rhs.r : r > rhs.r;
}
}query[N];
int main(){
int cs = 0;
for(_ = read(); _; _ --){
full(cnt, 0), full(res, 0);
n = read(), q = read();
scanf("%s", s + 1);
t = sqrt(n);
for(int i = 1; i <= q; i ++){
query[i].l = read(), query[i].r = read();
query[i].id = i, query[i].block = (query[i].l - 1) / t + 1;
}
sort(query + 1, query + q + 1);
int l = 1, r = 0;
for(int i = 1; i <= q; i ++){
int curL = query[i].l, curR = query[i].r;
while(l < curL) cnt[s[l++] - 'A'] --;
while(r < curR) cnt[s[++r] - 'A'] ++;
while(l > curL) cnt[s[--l] - 'A'] ++;
while(r > curR) cnt[s[r--] - 'A'] --;
for(int j = 0; j < 26; j ++){
if(cnt[j] != 0){
res[query[i].id] = cnt[j];
break;
}
}
}
printf("Case #%d:
", ++cs);
for(int i = 1; i <= q; i ++) printf("%d
", res[i]);
}
return 0;
}