莫队
直接莫队就好了。。统计每个字母出现的次数= =
#include#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 inline T max(T x, T y, T z){ return max(max(x, y), z); }template inline T min(T x, T y, T z){ return min(min(x, y), z); }template 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:\n", ++cs); for(int i = 1; i <= q; i ++) printf("%d\n", res[i]); } return 0;}