[uoj 429] runs (inclusive) + a little record about Lyndon tree and its application

String Division

Topic link ：UOJ 429

The main idea of the topic

Give you a string , Then ask how many divisions you have , Satisfy that two adjacent strings are not equal , And each string does not have a whole period .

Ideas

Lyndon Tree

$\mathrm{Lyndon}\mathrm{Tree}$ What is it? ？
It's that you can't put two strings $\mathrm{Ly}$ Put it together to get a new $\mathrm{Ly}$ Do you , Let's find the smallest suffix for a string （ It can't count itself ）, Then get two strings , Then keep dividing , Got it. $\mathrm{Lyndon}\mathrm{Tree}$.

Then this thing is built on this string is $\mathrm{Ly}$ On the basis of , If not, it is for $\mathrm{Ly}$ Do this for each string divided , Form a forest .

Then when you think about it, you will find that it is $\mathrm{SA}$ Of $\mathrm{rank}$ Array to build a Cartesian tree to get the tree .

Then there are some properties ：
If $[l,r]$ yes $\mathrm{Ly}$, that $l,r$ The character corresponds to the point on the tree $\mathrm{LCA}$ yes $a$（ set up ）, For substrings $[l_a,r_a]$, There will be $l=l_a⩽r_a⩽r$.
Then if this interval is ${\mathrm{Ly}}_{\mathrm{s},\mathrm{f}}(\mathrm{l})$（ It's not difficult to feel that this tree is also divided $f$ Of ）, It must be on the right son （ Because it is the longest $\mathrm{Ly}$ ah ）
Then it's almost the same , Any one $\mathrm{run}$ Of $\mathrm{LyR}$ It must appear in the right son （ This is right here $f\in \{0,1\}$ One of them ）, Then it seems to see that satisfaction $s_{r+1}{<}_f{s}_{r+1-p}$

---

It seems that I haven't said it before $\mathrm{WPL}$ and $\mathrm{PL}$, Here is a sentence .

For a string $S$ Yes $p,q$ Two cycles , If $p+q⩽|S|$, Then there are $\gcd (p,q)$ The cycle of （$\mathrm{WPL}$,$\mathrm{Weak}\mathrm{Periodicity}\mathrm{Lemma}$）
（ You can move a position by two cycles to get the minus position , And then divide them ）

Then it can actually be extended to $p+q-\gcd (p,q)⩽|S|$, Namely $\mathrm{PL}$,$\mathrm{PeriodicityLemma}$ 了 .
（ I don't know , It seems that the upper bound can be obtained by giving an example first , Then proportion Bala makes a connection ）

---

What's the use , One can be called “ Substring semi periodic query ” Things that are （Two-Period Queries）

This thing requires you to quickly query whether a substring has a period of no more than half its length , If there is one with the smallest output .

Let's define a $\mathrm{exrun}(i,j)$ To satisfy $i^{\prime }⩽i,j⩽j^{\prime },p⩽(j-i+1)/2$ One of the $\mathrm{run}({\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime },\mathrm{p})$.
Then we can prove that it is unique if it exists .
（ Because if it's not the only , Those that overlap can be used $\mathrm{WPL}$ Find contradictions ）

Then this definition can solve the above problem , Let's think about it $f\in \{0,1\}$ All built $\mathrm{Lyndon}\mathrm{Tree}$, And then let $a=\mathrm{lca}([i,\lceil (i+j)/2\rceil ])$, Then judge whether the right son meets the conditions .

As for this position, it can be judged because there must be a corresponding $\mathrm{LyR}$ contain $\lceil (i+j)/2\rceil$, According to the above properties , It will appear in the position of the right son at a certain point .
And then we'll find out $a$ Location will also $>p$, It also includes that location , therefore $a$ It would be this $\mathrm{LyR}$ The ancestors of the .
As long as its right son is not that $\mathrm{LyR}$, It will also be its ancestors .

That's because the right son can get bigger positions in turn .
If the one in the middle $⩽j$, Then its corresponding position is $p$ This cycle , Then it's not $\mathrm{Ly}$ 了 , contradiction .
If $>j$, that $\mathrm{LyR}$ The interval formed by its left boundary and its right boundary will be smaller than the interval formed by it , That is also related to it $\mathrm{Ly}$ There's a contradiction （ By definition ）.
So the opposite is true .

This question

This question is still very friendly ！
（ At least not a tree array ）

Consider how to find illegal , When you see the division, consider giving each divided string a function , Then the weight of a division is all multiplied （ In this way, illegal ones will be directly given $0$）
Then I found that if there is no whole cycle, I can do , But it is said that the two cannot be the same .

Considering that the same is very similar , If you combine two identical ones, the whole cycle ahead will be formed .
So you consider letting go , The situation of the whole cycle and the offset between the two .
Then think about it. It is not difficult to find that the tolerance exclusion coefficient is the number of occurrences of the minimum cyclic section of this string .

Then consider DP, It's not hard to get $n^2$ In the form of （ Enumerate where the new substring starts ）, Consider optimizing .
The first special thing is that there is a whole cycle , Then we can prefix and , Then subtract the one with the whole period .

Then consider the whole cycle , First turn on the $\mathrm{run}$ Find out , Then we can get some intervals .
Found that for a $\mathrm{run}$,$r$ It can provide an isochronous sequence where a point can be transferred from .
Then we only need for each $r$ Maintain the contribution and sum of the points of each arithmetic sequence that currently appears .
Then notice a point , The number of cycles of other previous points $+1$（ Or add one to all , The last one is from $0$ To $1$）, Then you can take it in reverse and add it .

Code

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define ll long long
#define mo 998244353
#define ull unsigned long long

using namespace std;

const int N = 2e5 + 100;
char s[N];
int n, ly[N], m;
struct RUNS {
    
	int x, y, p;
}runs[N << 1];
vector <int> ed[N];
vector <ll> sum[N << 1][2];
//0: Subtract the prefix and 
//1: A class  
ll f[N];

struct HASH {
    
	const int di = 131;
	ull mi[N], hash[N];
	
	void Init() {
    
		mi[0] = 1;
		for (int i = 1; i <= n; i++) {
    
			mi[i] = mi[i - 1] * di;
			hash[i] = hash[i - 1] * di + s[i] - 'a' + 1;
		}
	}
	
	ull get(int x, int y) {
    
		return hash[y] - hash[x - 1] * mi[y - x + 1];
	}
}H;

int getl(int x, int y) {
    
	int l = 1, r = min(x, y), re = 0;
	while (l <= r) {
    
		int mid = (l + r) >> 1;
		if (H.get(x - mid + 1, x) == H.get(y - mid + 1, y)) re = mid, l = mid + 1;
			else r = mid - 1;
	}
	return re;
}

int getr(int x, int y) {
    
	int l = 1, r = min(n - x + 1, n - y + 1), re = 0;
	while (l <= r) {
    
		int mid = (l + r) >> 1;
		if (H.get(x, x + mid - 1) == H.get(y, y + mid - 1)) re = mid, l = mid + 1;
			else r = mid - 1;
	}
	return re;
}

int sta[N];

bool cmpS(int x, int y) {
    
	int pl = getr(x, y);
	return s[x + pl] < s[y + pl];
}

void Lyndon(bool op) {
    
	sta[0] = 0; sta[++sta[0]] = n + 1; sta[++sta[0]] = n; ly[n] = n;
	for (int i = n - 1; i >= 1; i--) {
    
		while (sta[0] > 1 && cmpS(i, sta[sta[0]]) == op) sta[0]--;
		sta[++sta[0]] = i; ly[i] = sta[sta[0] - 1] - 1;
	}
}

void check(int x, int y) {
    
	int l = getl(x, y), r = getr(x, y);
	if (l + r >= y - x + 1) runs[++m] = (RUNS){
    x - l + 1, y + r - 1, y - x};
}

bool cmp_runs(RUNS x, RUNS y) {
    
	if (x.x != y.x) return x.x < y.x;
	if (x.y != y.y) return x.y < y.y;
	return x.p < y.p;
}

void Init() {
    
	H.Init();
	for (int op = 0; op <= 1; op++) {
    
		Lyndon(op);
		for (int i = 1; i <= n; i++) {
    
			check(i, ly[i] + 1);
		} 
	}
	sort(runs + 1, runs + m + 1, cmp_runs);
	int tmp = m; m = 0;
	for (int i = 1; i <= tmp; i++)
		if (runs[i].x != runs[i - 1].x || runs[i].y != runs[i - 1].y)
			runs[++m] = runs[i];
} 

int main() {
    
	scanf("%s", s + 1); n = strlen(s + 1);
	Init();
	
	for (int i = 1; i <= m; i++) {
    
		for (int r = runs[i].x + 2 * runs[i].p - 1; r <= runs[i].y; r++)
			ed[r].push_back(i);
		int sz = runs[i].p;
		if (runs[i].y - (runs[i].x + 2 * runs[i].p - 1) + 1 <= runs[i].p)
			sz = (runs[i].y - runs[i].x + 1) % runs[i].p;
		sz++;
		sum[i][0].resize(sz); sum[i][1].resize(sz);
	}
	
	f[0] = 1; ll Sum = 1;
	for (int i = 1; i <= n; i++) {
    
		f[i] = Sum;
		for (int j = 0; j < ed[i].size(); j++) {
     int v = ed[i][j];
			int l = runs[v].x, r = runs[v].y, p = runs[v].p;
			int id = (i - l + 1) % p;
			(sum[v][0][id] += mo - f[i - 2 * p]) %= mo;
			(sum[v][1][id] *= mo - 1) %= mo; (sum[v][1][id] += mo - f[i - 2 * p]) %= mo;
			(f[i] += sum[v][0][id] + sum[v][1][id]) %= mo;
		}
		(Sum += f[i]) %= mo;
	}
	printf("%lld", f[n]);
	
	return 0;
}