后缀数组、set、离散
题解：
分析：
首先让我们看看这一题要求的是什么。每一个索引到最左端能构成的魔咒的数量。
看到这里我们应该能反应过来。抓住不变的东西，最左端是始终不变的。
如果我们把字符串reverse一下，那么求的就是每一个后缀的魔咒数量了！！！
很明显的线索
那么就让我们来思考一下反转后字符串的后缀i与后缀i-1吧。
我们清楚，在后缀i-1中的子串也一定在后缀i中！
那么我们要求后缀i中没有的(子串)。
这些子串一定都是以s[n-i-1]（就是后缀的开头）为最左端的。废话
以i为最右端的字串一共有i个候选，我们要知道有多少个在后缀i-1中已经出现过了。
其实就是后缀i与后缀1，2，3，，，，i-1的最大的最长公共前缀长度！！！！
对吧。并不是难理解的。如果没能理解建议画图按步骤梳理，讲的有点不好。
但是我们却发现，这里是很耗时的！！
我们绝对不能一一枚举后缀1,2,3,4,,,,,i-1。虽然我们可以利用st表实现常数查询但是也伤不起。
那么我们就想想吧，该怎么办？
从最长公共前缀的求法出发，我们想想解决对策。
后缀i的排名rki
那么对于后缀1到i-1他们的排名rk1到rki-1
只有两种可能，一个是排名比rki高一个是排名比rki低废话
再回想一下如何求最长公共前缀长度，两端排名区间的最小值。
我们要求这些区间最小值的最大值。那么就很明显了，我们只要保留离rki最近的两个排名
一个大于rki记为rkl一个小于rki记为rkr然后我们查询一下[rkl+1,rki]与 [rki+1,rkr]就能找到最大值了。
为什么这样呢？因为对于其他的所有排名大于rki的后缀求最长公共后缀时一定要经过rkl
同理对于其他排名小于rki的后最求最长公共后缀时一定要经过rkr
那么他们与后缀i的最长公共前缀相较于rkl与rkr只会只小不增。毕竟求的是最小值嘛。
那么得解。
具体我是利用set进行的操作。在维护有序的同时，使用二分查找确定rkl与rkr。
注意set中使用二分查找只能使用set方法，stl中的二分查找函数会退化致O(n)级别
另外因为给的数据中 x的大小在[1,1e9]之间，所以我们还要离散一下
##代码如下：
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define re register
const int max_n = 1e5 + 100;
typedef long long ll;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while (!isdigit(c)) { if (c == '-')f = -1;c = getchar(); }
while (isdigit(c))x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return x * f;
}
inline void write(int x) {
int num = 0;char c[15];
while (x)c[++num] = (x % 10) + 48, x /= 10;
while (num)putchar(c[num--]);
putchar('\n');
}
int ranks[max_n], SA[max_n], height[max_n];
int wa[max_n], wb[max_n], wvarr[max_n], wsarr[max_n];
inline int cmp(int* r, int a, int b, int l) {
return r[a] == r[b] && r[a + l] == r[b + l];
}
inline void get_sa(int* r, int* sa, int n, int m) {
++n;
re int i, j, p, * x = wa, * y = wb, * t;
for (i = 0; i < m; ++i) wsarr[i] = 0;
for (i = 0; i < n; ++i) wsarr[x[i] = r[i]]++;
for (i = 1; i < m; ++i) wsarr[i] += wsarr[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wsarr[x[i]]] = i;
for (j = 1, p = 1; p < n; j <<= 1, m = p) {
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; ++i) wvarr[i] = x[y[i]];
for (i = 0; i < m; ++i) wsarr[i] = 0;
for (i = 0; i < n; ++i) wsarr[wvarr[i]]++;
for (i = 1; i < m; ++i) wsarr[i] += wsarr[i - 1];
for (i = n - 1; i >= 0; --i) sa[--wsarr[wvarr[i]]] = y[i];
for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
}//求解高度数组，height[i]指排名
inline void get_height(int* r, int* sa, int n) {
re int i, j, k = 0;
for (i = 1; i <= n; ++i) ranks[sa[i]] = i;
for (i = 0; i < n; height[ranks[i++]] = k)
for (k ? k-- : 0, j = sa[ranks[i] - 1]; r[i + k] == r[j + k]; k++);
return;
}
int st[max_n][32];
void initSt(int a[], int n) {
for (int i = 0;i <= n;++i)st[i][0] = a[i];
int mxk = (int)log2(n + 1);
for (int k = 1;k <= mxk;++k) {
for (int i = 0;i <= n;++i) {
if (i + (1 << k) - 1 > n)break;
st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
}
}
int que(int l, int r) {
int len = log2(r - l + 1);
return min(st[l][len], st[r - (1 << len) + 1][len]);
}
int a[max_n];
int b[max_n];
int main() {
ios::sync_with_stdio(0);
int n = read();
map<int, int> mp;
for (re int i = n - 1;i >= 0;--i)a[i] = read();
for (re int i = 0;i < n;++i)b[i] = a[i];
sort(b, b + n);
int tot = 0;
for (re int i = 0;i < n;++i)if (!mp[b[i]])mp[b[i]] = ++tot;
for (re int i = 0;i < n;++i)a[i] = mp[a[i]];
get_sa(a, SA, n, tot + 2);
get_height(a, SA, n);
initSt(height, n);
set<int> myset1;
set<int> myset2;
set<int>::iterator it;
ll ans = 0;
for (re int i = n - 1;i >= 0;--i) {
int rk = ranks[i];
int len = 0;
it = myset1.upper_bound(rk);
if (it != myset1.end())
len = max(len, que(rk + 1, *it));
it = myset2.upper_bound(-rk);
if (it != myset2.end())
len = max(len, que(-(*it) + 1, rk));
myset1.insert(rk);
myset2.insert(-rk);
ans += n - i - len;
write(ans);
}
}
京公网安备 11010502036488号