Contest Duration: - (local time) (100 minutes) Back to Home

F - Common Prefixes Editorial by Feecle6418

Let’s first compute suffix array of the string and the height array $$(h_i=LCP(suf_{sa_i},suf_{sa_{i-1}}))$$. Here $$sa$$ is the suffix array (index starts from 1), $$suf$$ is the suffix of the string, $$LCP$$ is longest common prefix. Let $$rnk_{sa_i}=i$$.

There is a well-known conclusion that $$LCP(suf_i,suf_j)(rnk_i<rnk_j)$$ is the minimum of $$h_{rnk_{i+1}},h_{rnk_{i+2}},\dots,h_{rnk_j}$$,

By considering the suffixes in the order of $$rnk$$, we can rewrite the problem to:

Given $$n$$ integers $$a_1\sim a_n$$, for every $$i$$ compute $$\sum_{j=1}^n \min_{k=\min(i,j)}^{\max(i,j)} a_k$$.

This can be solved easily with a stack in linear time.

The total time complexity is $$O(n+SA(n))$$, where $$SA(n)$$ is the time complexity you use to compute suffix arrays.

posted:
last update: