子串查詢
?
?Accepts: 1262
?
?Submissions: 5335
?Time Limit: 3500/3000 MS (Java/Others)
?
?Memory Limit: 262144/262144 K (Java/Others)
Problem Description
度度熊的字符串課堂開始了！要以像度度熊一樣的天才為目標，努力奮斗哦！
為了檢驗你是否具備不聽課的資質，度度熊準備了一個只包含大寫英文字母的字符串?A[1,n] = a_1 a_2 \cdots a_nA[1,n]=a?1??a?2???a?n??，接下來他會向你提出?qq?個問題?(l,r)(l,r)，你需要回答字符串?A[l,r] = a_l a_{l+1} \cdots a_rA[l,r]=a?l??a?l+1???a?r???內有多少個非空子串是?A[l,r]A[l,r]?的所有非空子串中字典序最小的。這里的非空子串是字符串中由至少一個位置連續的字符組成的子序列，兩個子串是不同的當且僅當這兩個子串內容不完全相同或者出現在不同的位置。
記?|S|∣S∣?為字符串?SS?的長度，對于兩個字符串?SS?和?TT?，定義?SS?的字典序比?TT?小，當且僅當存在非負整數?k(\leq \min(|S|,|T|))k(≤min(∣S∣,∣T∣))?使得?SS?的前?kk?個字符與?TT?的前?kk?個字符對應相同，并且要么滿足?|S| = k∣S∣=k?且?|T| > k∣T∣>k，要么滿足?k < \min(|S|,|T|)k<min(∣S∣,∣T∣)?且?SS?的第?k+1k+1?個字符比?TT?的第?k+1k+1?個字符小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。
Input
第一行包含一個整數?TT，表示有?TT?組測試數據。
接下來依次描述?TT?組測試數據。對于每組測試數據：
第一行包含兩個整數?nn?和?qq，表示字符串的長度以及詢問的次數。
第二行包含一個長為?nn?的只包含大寫英文字母的字符串?A[1,n]A[1,n]。
接下來?qq?行，每行包含兩個整數?l_i,r_il?i??,r?i??，表示第?ii?次詢問的參數。
保證?1 \leq T \leq 101≤T≤10，1 \leq n,q \leq 10^51≤n,q≤10?5??，1 \leq l_i \leq r_i \leq n1≤l?i??≤r?i??≤n。
Output
對于每組測試數據，先輸出一行信息 "Case #x:"（不含引號），其中 x 表示這是第?xx?組測試數據，接下來?qq?行，每行包含一個整數，表示字符串?A[l,r]A[l,r]?中字典序最小的子串個數，行末不要有多余空格。
Sample Input
1 2 3 AB 1 1 1 2 2 2Sample Output
Copy
Case #1: 1 1 1
前綴字母A~Z的個數，復雜度（O(n)）
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define fora(i,a,b) for(i=a;i<b;i++)
#define fors(i,a,b) for(i=a;i>b;i--)
#define fora2(i,a,b) for(i=a;i<=b;i++)
#define fors2(i,a,b) for(i=a;i>=b;i--)
#define PI acos(-1.0)
#define eps 1e-6
#define INF 0x3f3f3f3ftypedef long long LL;
typedef long long LD;
using namespace std;
const int maxn=1e5+11;
char str[maxn];
int qz[maxn][33];
int main()
{int T,t=0,len;scanf("%d",&T);while(T--){int n,q;scanf("%d%d%s",&n,&q,str);int i,j;len=strlen(str);fora(i,0,len){fora(j,0,26){qz[i+1][j]=qz[i][j];}qz[i+1][str[i]-'A']++;}printf("Case #%d:\n",++t);while(q--){int L,R;scanf("%d%d",&L,&R);fora(i,0,26){//printf("****%c %d %d\n",i+'A',qz[R+1][i],qz[L][i]);if(qz[R][i]-qz[L-1][i]>0){printf("%d\n",qz[R][i]-qz[L-1][i]);break;}}}}return 0;
}
?
