[NOI 2016] 우수한 분할 접미사 자동 트 리 에 계발 식 병합 선분 트 리

[NOI 2016] 우수한 분할
제목 전송 문 luogu bzoj
분석 하 다.
이 문 제 는 Hash, 접미사 배열 이 든 자동 동기 든 인터넷 의 대부분 문 제 는 관건 점 + 조화 급수 라 는 조작 을 사용 했다.본 건 33951 건 33979 건 은 관건 이 생각 나 지 않 기 때문에 비교적 번 거 로 운 O (n l o g 2) O (nlog ^ 2) O (nlog 2) O (nlog 2) 방법 을 사용 합 니 다.
먼저 문 제 를 모든 i i 에 대해 i i 를 경계 로 하 는 A A AA AA 구조의 개수 로 바 꿀 것 입 니 다. 물론 접두사 접 두 사 는 각각 한 번 구하 고 아래 는 기본 접두사 입 니 다.
형식화 문 제 를 고려 해 어떤 접두사 i i i 에 대해 서 는 모든 접두사 j (j < i) j (j < i) j (j < i) j (j < i) j (j < i) 를 구하 고, i, j i, j i, j, j, j, j 의 가장 긴 공공 접두사 의 길이 가 j - i j - i - i 보다 크 면, 즉 879 {j: 87j < i, i, i - j ≤ * * * * * * * *, i - j, j - j, j, l c s (S 1, j, S 1, i, i) * * * \ \ \ {j | j, i, i, i, i, i \ \ \ \ l l l l l l l l l | | | | \ \ \ \ \ \ {j, i, i, i, i \ l l 8739 ° j, 8739 ° j < i, i − j ≤ 8739 ° Lcs (S1, j, S1, i)∣}∣
접두사 접두사 문제 에 대해 서 는 일반적으로 접두사 자동 동기 p a r e n t parent parent 트 리 에 접두사 자동 동기 p a r e n t parent parent 트 리 를 고려 합 니 다. 접두사 자동 동기 p a r e n t parent 트 리 는 접두사 마다 T r i e Trie Trie 트 리 에 역순 으로 삽입 하 는 것 과 같 기 때문에 두 접두사 의 L c s Lcs Lcs 는 그들 p a r e n t parent 트 리 에 있 는 L c a Lca Lca 에 대응 합 니 다.
그래서 트 리 에 몇 개의 관건 점 (문자열 의 접두사 에 대응) 을 주 고 각 x x x x x 에 대해 {y * 8739 ° m x x - m x y ≤ m x l c a (x, y)} \ {y | mx x - mx y \ le mx {lca (x, y)} \ \} {y * 8739 ° mxx - mxy ≤ mxlca (x, y)} 을 구 합 니 다.
트 리 의 계발 식 합병 을 고려 하여 각 노드 에 동적 오픈 라인 트 리 를 만 듭 니 다. 우 리 는 아버지 로 하여 금 무 거 운 아들 의 라인 트 리 를 계승 하고 다른 서브 트 리 의 라인 트 리 노드 를 폭력 적 으로 합병 하 게 합 니 다.
특정한 노드 를 삽입 할 때 라인 트 리 안의 노드 가 그 에 대한 기여 와 라인 트 리 안의 노드 에 대한 기 여 를 고려 합 니 다.전 자 는 한 구간 으로 물 어보 면 됩 니 다. 그렇지 않 으 면 선분 나무 에 표 시 를 하지만 이 선분 나 무 는 뜯 어 질 때 폭력 표 시 를 내 려 답 에 기여 하면 됩 니 다.
각 노드 가 삽 입 된 후 소재 선분 트 리 의 크기 가 배가 되 기 때문에 l o g log 를 많이 삽입 합 니 다. 총 복잡 도 O (n l o g 2) O (nlog ^ 2) O (nlog 2)
코드

#include
const int N = 6e4 + 10, T = 1e6 + 10;
int ri() {
	char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
	for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f;
}
int nx[N], pr[N], fa[N], ch[N][26], st[N], rt[N], mx[N], ans1[N], ans2[N];
int ls[T], rs[T], cnt[T], tag[T], tp, *tot, top, n, last, sz;
bool val[N]; char s[N];
void Clear() {
	top = last = 1; pr[1] = 0;
	memset(ch[1], 0, sizeof(ch[1]));
	sz = 0;
	for(int i = 1;i <= n; ++i)
		tot[i] = 0;
}
void Push(int p) {
	if(tag[p]) {
		if(ls[p])
			tag[ls[p]] += tag[p];
		if(rs[p])
			tag[rs[p]] += tag[p];
		tag[p] = 0;
	}
}
void Get(int p, int L, int R) {
	if(L == R) {
		tot[L] += tag[p];
		st[++tp] = L;
		return ;
	}
	int m = L + R >> 1; Push(p);
	if(ls[p])
		Get(ls[p], L, m);
	if(rs[p])
		Get(rs[p], m + 1, R);
}
void Ins(int &p, int L, int R, int x) {
	if(!p) {p = ++sz; ls[p] = rs[p] = tag[p] = cnt[p] = 0;}
	++cnt[p]; if(L == R) return ;
	int m = L + R >> 1; Push(p);
	if(x <= m) Ins(ls[p], L, m, x);
	else Ins(rs[p], m + 1, R, x);
}
void Modify(int p, int L, int R, int st, int ed) {
	if(L == st && ed == R)
		return ++tag[p], void();
	int m = L + R >> 1; Push(p);
	if(st <= m && ls[p])
		Modify(ls[p], L, m, st, std::min(ed, m));
	if(ed > m && rs[p])
		Modify(rs[p], m + 1, R, std::max(st, m + 1), ed);
}
int Query(int p, int L, int R, int st, int ed) {
	if(L == st && ed == R)
		return cnt[p];
	int m = L + R >> 1, ans = 0;
	if(st <= m && ls[p])
		ans += Query(ls[p], L, m, st, std::min(ed, m));
	if(ed > m && rs[p])
		ans += Query(rs[p], m + 1, R, std::max(st, m + 1), ed);
	return ans;
}
void Extend(int c) {
	int p = last, np = last = ++top; 
	memset(ch[np], 0, sizeof(ch[np])); pr[np] = 0;
	mx[np] = mx[p] + 1; rt[np] = 0; val[np] = true;
	for(;p && !ch[p][c]; p = fa[p])
		ch[p][c] = np;
	if(!p) fa[np] = 1;
	else {
		int q = ch[p][c];
		if(mx[q] == mx[p] + 1) 
			fa[np] = q;
		else {
			int nq = ++top; mx[nq] = mx[p] + 1;
			memcpy(ch[nq], ch[q], sizeof(ch[nq]));
			rt[nq]  = 0; val[nq] = false; pr[nq] = 0;
			fa[nq] = fa[q];
			fa[q] = fa[np] = nq;
			for(;ch[p][c] == q; p = fa[p])
				ch[p][c] = nq;
		}
	}
}
void Merge(int rt, int x, int c) {
	if(x - c)
		tot[x] += Query(rt, 1, n, x - c, x);
	Modify(rt, 1, n, x, std::min(n, x + c));
}
void Dfs(int u) {
	if(!pr[u])
		return Ins(rt[u], 1, n, mx[u]);
	int ds = 0;
	for(int i = pr[u]; i; i = nx[i]) {
		Dfs(i);
		if(cnt[rt[i]] > cnt[rt[ds]])
			ds = i;
	}
	rt[u] = rt[ds];
	for(int i = pr[u]; i; i = nx[i]) 
		if(i != ds){
			tp = 0; Get(rt[i], 1, n);
			for(int x = 1; x <= tp; ++x)
				Merge(rt[u], st[x], mx[u]);
			for(int x = 1;	x <= tp; ++x)
				Ins(rt[u], 1, n, st[x]);
		}
	if(val[u]) {
		Merge(rt[u], mx[u], mx[u]); 
		Ins(rt[u], 1, n, mx[u]);
	}
}
void Work() {
	Clear();
	for(int i = 1; i <= n; ++i)
		Extend(s[i] - 'a');
	for(int i = 2;i <= top; ++i)
		nx[i] = pr[fa[i]], pr[fa[i]] = i;
	Dfs(1); tp = 0; Get(rt[1], 1, n);
}
int main() {
	for(int T = ri(); T--; ) {
		scanf("%s", s + 1); n = strlen(s + 1);
		tot = ans1; Work();
		std::reverse(s + 1, s + n + 1);
		tot = ans2; Work();
		long long ans = 0;
		for(int i = 1;i <= n; ++i)
			ans += 1LL * ans1[i] * ans2[n - i];
		printf("%lld
", ans);
	}
	return 0;
}