毒瘤sdoi 终于有一道我会做的题啦qwq
首先，本质不同的子串的个数 $ = \frac{n(n + 1)}{2} - \sum height[i]$
把原串翻转过来，每次就相当于添加一个后缀
然后直接用set xjb维护一下前驱后继就行了
时间复杂度：\(o(nlogn)\)
我要评论// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define sit set<int>::iterator
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 2333;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int n, m, l, rak[maxn], tax[maxn], tp[maxn], sa[maxn], h[maxn], f[maxn][20], lg2[maxn], s[maxn], date[maxn], ans[maxn];
set<int> st;
void qsort() {
for(int i = 0; i <= m; i++) tax[i] = 0;
for(int i = 1; i <= n; i++) tax[rak[i]]++;
for(int i = 1; i <= m; i++) tax[i] += tax[i - 1];
for(int i = n; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
}
void suffixsort() {
for(int i = 1; i <= n; i++) rak[i] = s[i], tp[i] = i; m = 233; qsort();
for(int w = 1, p = 0; p < n; w <<= 1, m = p) { p = 0;
for(int i = 1; i <= w; i++) tp[++p] = n - i + 1;
for(int i = 1; i <= n; i++) if(sa[i] > w) tp[++p] = sa[i] - w;
qsort(); swap(tp, rak); rak[sa[1]] = p = 1;
for(int i = 2; i <= n; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p;
}
for(int i = 1, k = 0; i <= n; i++) {
if(k) k--; int j = sa[rak[i] - 1];
while(s[i + k] == s[j + k]) k++;
h[rak[i]] = k;
}
}
void pre() {
for(int i = 1; i <= n; i++) f[i][0] = h[i];
for(int j = 1; j <= 17; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int x, int y) {
if(x > y) swap(x, y); x++;
int k = lg2[y - x + 1];
return min(f[x][k], f[y - (1 << k) + 1][k]);
}
void des() {
sort(date + 1, date + n + 1);
int num = unique(date + 1, date + n + 1) - date - 1;
for(int i = 1; i <= n; i++) s[i] = lower_bound(date + 1, date + num + 1, s[i]) - date;
reverse(s + 1, s + n + 1);
}
int main() {
lg2[1] = 0; for(int i = 2; i <= maxn - 1; i++) lg2[i] = lg2[i >> 1] + 1;
n = read();
for(int i = 1; i <= n; i++) s[i] = date[i] = read();
des();
suffixsort(); pre();
st.insert(0); st.insert(n + 1);
ll now = 0; st.insert(rak[n]); ans[n] = 1;
printf("%lld\n", 1);
for(int i = n - 1; i >= 1; i--) {
sit nxt = st.upper_bound(rak[i]), pre;
if(*nxt == 0) pre = st.begin();
else pre = --nxt, nxt++;
// printf("%d %d\n", *pre, *nxt);
if(*pre != 0 && *nxt != n + 1) now -= query(*pre, *nxt);
if(*pre != 0 && *pre != n + 1) now += query(*pre, rak[i]);
if(*nxt != 0 && *nxt != n + 1) now += query(rak[i], *nxt);
printf("%lld\n", 1ll * (n - i + 1) * ((n - i + 1) + 1) / 2 - now);
st.insert(rak[i]);
}
return 0;
}
/*
4
1 2 3 3
3
1 3 1
*/
如对本文有疑问， 点击进行留言回复！！
FPGA/verilog 学习笔记（1）—— FPGA和HDL基础概念
2020年 浙江工业大学计算机科学与技术学硕 初试复试经验帖
网友评论