B. 攻防演练 （2021CCPC女生赛）

题意：

给出一个长度为n的字符，字符是前m个小写字母，有q个询问，每次询问一个最短子序列的长度满足不是[l,r]内任意一个子序列

思路：

[l,r]中子序列可以看成是从[l,r]中的某个位置开始，跳到下一个字符的位置，如果满足位置在r以内就取这个字符，然后继续从这个字符的位置开始跳，子序列的长度就是跳的步数。

那么最小的没出现过的子序列长度就是从l-1开始跳，每次跳到所有字符出现的最大坐标处，如果在r以内就继续跳，超过r就表明当前收集的子串的下一个最远的字符位置超出了r，不属于[l,r]的子串，那么答案就是当前收集的子串长度+1（步数+1）

用nxt[i][j]表示从第i个位置往后的下一个字符为j的坐标，那么我们从后往前处理

用f[i][j]表示从第i个位置开始走，走2^j步能走到的最大坐标，先预处理f[i][0]，转换方程是f[i][j]=f[f[i][j-1]][j-1]

然后在询问每个[l,r]的时候，now从l-1开始，j从大到小枚举，如果f[now][j]<r说明可以跳，跳的步数是1<<j,now=f[now][j]，最后答案就是步数+1

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,q;
string s;
int nxt[N][30];
int f[N][30];
int pos[30];
void sove(){cin>>m>>n;cin>>s;s=" "+s;for(int i=0;i<m;i++)nxt[n][i]=n+1;for(int i=n;i>=1;i--){pos[s[i]-'a']=i;for(int j=0;j<m;j++){if(pos[j])nxt[i-1][j]=pos[j];else nxt[i-1][j]=n+1;
//			cout<<"i-1=="<<i-1<<" j=="<<j<<" nxt="<<nxt[i-1][j]<<endl;}}for(int i=0;i<=n;i++){int mx=0;for(int j=0;j<m;j++)mx=max(mx,nxt[i][j]);f[i][0]=mx;
//		cout<<"i=="<<i<<" f=="<<f[i][0]<<endl;for(int j=0;j<19;j++) f[n][j]=f[n+1][j]=n+1;}for(int j=1;j<19;j++){for(int i=0;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];
//			cout<<"i=="<<i<<" j=="<<j<<" f="<<f[i][j]<<endl;}}cin>>q;while(q--){int ans=0;int l,r;cin>>l>>r;int now=l-1;for(int j=18;j>=0;j--){if(f[now][j]<=r){
//				cout<<"now=="<<now<<" j=="<<j<<" f=="<<f[now][j]<<endl;ans+=1<<j;now=f[now][j];}}cout<<ans+1<<endl;}
}
int main(){ios::sync_with_stdio(false);cin.tie(),cout.tie();int t=1;
//	cin>>t;while(t--){sove();}return 0;
}