#2033. 「SDOI2016」生成魔咒
题目描述
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1 11、2 22 拼凑起来形成一个魔咒串 [1,2] [1, 2][1,2]。
一个魔咒串 S SS 的非空子串被称为魔咒串 S SS 的生成魔咒。
例如 S=[1,2,1] S = [1, 2, 1]S=[1,2,1] 时，它的生成魔咒有 [1] [1][1]、[2] [2][2]、[1,2] [1, 2][1,2]、[2,1] [2, 1][2,1]、[1,2,1] [1, 2, 1][1,2,1] 五种。S=[1,1,1] S = [1, 1, 1]S=[1,1,1] 时，它的生成魔咒有 [1] [1][1]、[1,1] [1, 1][1,1]、[1,1,1] [1, 1, 1][1,1,1] 三种。
最初 S SS 为空串。共进行 n nn 次操作，每次操作是在 S SS 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 S SS 共有多少种生成魔咒。
输入格式
第一行一个整数 n nn。
第二行 n nn 个数，第 i ii 个数表示第 i ii 次操作加入的魔咒字符。
输出格式
输出 n nn 行，每行一个数。第 i ii 行的数表示第 i ii 次操作后 S SS 的生成魔咒数量。
样例
样例输入
7
1 2 3 3 3 1 2样例输出
1
3
6
9
12
17
22数据范围与提示
对于 10% 10\%10% 的数据，1≤n≤10 1 \leq n \leq 101≤n≤10；
对于 30% 30\%30% 的数据，1≤n≤100 1 \leq n \leq 1001≤n≤100；
对于 60% 60\%60% 的数据，1≤n≤1000 1 \leq n \leq 10001≤n≤1000；
对于 100% 100\%100% 的数据，1≤n≤100000 1 \leq n \leq 1000001≤n≤100000。
用来表示魔咒字符的数字 x xx 满足 1≤x≤109 1 \leq x \leq 10 ^ 91≤x≤109。
题解：
离线，将插入过程变化为删除过程
那就最开始就是一个长度为n的字符串让你求不重复字串个数
利用后缀数组height[i]值可以求解
那么每次删除的时候， 将位置为i的字符从 sa中删除，找到前一个存在的，和后一个存在的字符后缀串，fi,se
那么答案更新就是
ans = ans + lcp(fi,rank[i]) + lcp(ran[k],se) - lcp(fi,se);
可以用set删，存位置
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,double>
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 1e5+, M = 1e3+,inf = 2e9; int *ran,r[N],sa[N],height[N],wa[N],wb[N],wm[N];
bool cmp(int *r,int a,int b,int l) {
return r[a] == r[b] && r[a+l] == r[b+l];
}
void SA(int *r,int *sa,int n,int m) {
int *x=wa,*y=wb,*t;
for(int i=;i<m;++i)wm[i]=;
for(int i=;i<n;++i)wm[x[i]=r[i]]++;
for(int i=;i<m;++i)wm[i]+=wm[i-];
for(int i=n-;i>=;--i)sa[--wm[x[i]]]=i;
for(int i=,j=,p=;p<n;j=j*,m=p){
for(p=,i=n-j;i<n;++i)y[p++]=i;
for(i=;i<n;++i)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=;i<m;++i)wm[i]=;
for(i=;i<n;++i)wm[x[y[i]]]++;
for(i=;i<m;++i)wm[i]+=wm[i-];
for(i=n-;i>=;--i)sa[--wm[x[y[i]]]]=y[i];
for(t=x,x=y,y=t,i=p=,x[sa[]]=;i<n;++i) {
x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p-:p++;
}
}
ran=x;
}
void Height(int *r,int *sa,int n) {
for(int i=,j=,k=;i<n;height[ran[i++]]=k)
for(k?--k:,j=sa[ran[i]-];r[i+k] == r[j+k];++k);
}
int n,a[N],san[N];
LL ans;
vector<LL > an;
int dp[N][];
void Lcp_init() {
for(int i = ; i <= n; ++i) dp[i][] = height[i];
for(int j = ; (<<j) <= n; ++j) {
for(int i = ; i + (<<j) - <= n; ++i) {
dp[i][j] = min(dp[i][j-],dp[i+(<<(j-))][j-]);
}
}
}
int lcp(int l,int r) {
l++;
if(l > r) swap(l,r); int len = r - l + ;
int k = ;
while((<<(k+)) <= len) k++;
return min(dp[l][k],dp[r - (<<k) + ][k]);
}
int main() {
scanf("%d",&n);
for(int i = ; i <= n; ++i) scanf("%d",&a[i]);
for(int i = ; i <= n; ++i) san[i] = a[i]; sort(san+,san+n+);
int SAs = unique(san+,san+n+) - san - ;
for(int i = ; i <= n; ++i)
a[i] = lower_bound(san+,san+SAs+,a[i]) - san;
int len = ;
for(int i = ; i <= n; ++i) r[len++] = a[n - i + ];
r[len] = ;
SA(r,sa,len+,n+);
Height(r,sa,n);
Lcp_init();
for(int i = ; i <= len; ++i) ans = ans + i - height[i];
set<int > s;
s.clear();
s.insert(-);
s.insert(inf);
for(int i = ; i <= len; ++i) s.insert(i);
an.push_back(ans);
for(int i = ; i < n; ++i) {
s.erase(ran[i-]);
int fi = *(--s.lower_bound(ran[i-]));
int se = *(s.lower_bound(ran[i-]));
ans = ans - (n - i + );
if(fi != -) ans += lcp(fi,ran[i-]);
if(se != inf) ans += lcp(ran[i-],se);
if(fi != - && se != inf) ans -= lcp(fi,se);
an.push_back(ans);
}
for(int i = an.size()-; i >= ; --i)
printf("%lld\n",an[i]);
return ;
}