题意：一个只含e, a, s, y的字符串，问[l, r]内有多少个easy序列？
题解：倍增。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 char s[N]; 5 int id(char c){ 6 if(c == 'e') return 0; 7 if(c == 'a') return 1; 8 if(c == 's') return 2; 9 return 3; 10 } 11 int Log[N]; 12 int f[17][N], nex[N][4]; 13 int main(){ 14 for(int i = 2; i < N; i++) Log[i] = Log[i>>1]+1; 15 scanf("%s", s+1); 16 int len = strlen(s+1); 17 int last[4]; 18 last[0] = last[1] = last[2] = last[3] = len+1; 19 for(int i = len; i; i--){ 20 int k = id(s[i]); 21 last[k] = i; 22 for(int j = 0; j < 4; j++) 23 nex[i][j] = last[j]; 24 } 25 //nex[i][k]: [i, len]中第一个k出现的位置 26 for(int i = 1; i <= len; i++){ 27 f[0][i] = nex[i][0]; 28 for(int j = 1; j < 4&&f[0][i] <= len; j++) 29 f[0][i] = nex[f[0][i]][j]; 30 } 31 //f[0][i]: [i, len]中第一个出现easy的结尾处 32 for(int j = 1; j <= Log[len]; j++) 33 for(int i = 1; i <= len; i++){ 34 int pos = f[j-1][i]; 35 f[j][i] = pos > len? pos : f[j-1][pos]; 36 } 37 38 int m, l, r; 39 scanf("%d", &m); 40 while(m--){ 41 scanf("%d%d", &l, &r); 42 int ans = 0; 43 for(int i = Log[len]; i >= 0&&l < r; i--){ 44 if(f[i][l] > r) continue ; 45 ans += 1<<i; 46 l = f[i][l]+1; 47 } 48 printf("%d ", ans); 49 } 50 return 0; 51 }