4516: [Sdoi2016]生成魔咒

题意：询问一个字符串每个前缀有多少不同的子串

---

做了一下SDOI2016R1D2，题好水啊随便AK

强行开map上SAM

每个状态的贡献就是\(Max(s)-Min(s)+1\)

插入的时候维护一下就行了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <map>

using namespace std;

typedef long long ll;

#define fir first

#define sec second

const int N=3e5+5, P=1e9+7;

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, s[N]; ll ans;

struct meow { map<int, int> ch; int par, val;}t[N];

int sz=1, root=1, last=1;

void extend(int c) {

	int p=last, np=++sz;

	t[np].val = t[p].val+1;

	for(; p && !t[p].ch[c]; p=t[p].par) t[p].ch[c]=np;

	if(!p) t[np].par = root;

	else {

		int q=t[p].ch[c];

		if(t[q].val == t[p].val+1) t[np].par=q;

		else {

			ans -= t[q].val - t[p].val;

			int nq=++sz; t[nq]=t[q]; t[nq].val = t[p].val+1;

			t[q].par = t[np].par = nq;

			ans += t[q].val - t[nq].val; ans ++;

			for(; p && t[p].ch[c]==q; p=t[p].par) t[p].ch[c] = nq;

		}

	}

	ans+=t[np].val - t[t[np].par].val;

	last=np;

}

int main() {

	//freopen("in","r",stdin);

	freopen("incantation.in","r",stdin);

	freopen("incantation.out","w",stdout);

	n=read();

	for(int i=1; i<=n; i++) {

		s[i]=read();

		extend(s[i]);

		printf("%lld\n",ans);

	}

}