题目描述：
给出S的SA，求S最少的不同字符的个数。 1<=n<=100000
题解：
SA的性质题，竟然不会。 有了SA，逆推可知rank。 如果rank[SA[i] + 1] >= rank[SA[i + 1] + 1] 则必有S[SA[i]] < S[SA[i + 1]] 于是我们扫一遍统计答案就好了。
Code：
#include<cstdio>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;
const int Maxn =
100005;
int n, SA[Maxn], rank[Maxn];
int main() {
for(
scanf(
"%d", &n); n;
scanf(
"%d", &n)) {
fo(i,
1, n)
scanf(
"%d", &SA[i]);
fo(i,
1, n) rank[SA[i]] = i; rank[n +
1] =
0;
int ans =
1;
fo(i,
1, n -
1)
if(rank[SA[i] +
1] >= rank[SA[i +
1] +
1]) ans ++;
printf(
"%d\n", ans);
}
}
