Mahmoud and Ehab and the final stage
Contest: Codeforces Round 435 (Div. 2)
Difficulty rating: 2900
Tags: data structures, strings

Mahmoud and Ehab solved Dr. Evil's questions so he gave them the password of the door of the evil land. When they tried to open the door using it, the door gave them a final question to solve before they leave (yes, the door is digital, Dr. Evil is modern). If they don't solve it, all the work will be useless and they won't leave the evil land forever. Will you help them?

Mahmoud and Ehab are given n strings s1, s2, ... , sn numbered from 1 to n and q queries, Each query has one of the following forms:

- 1 a b (1 ≤ a ≤ b ≤ n), For all the intervals [l;r] where (a ≤ l ≤ r ≤ b) find the maximum value of this expression:(r - l + 1) * LCP(sl, sl + 1, ... , sr - 1, sr) where LCP(str1, str2, str3, ... ) is the length of the longest common prefix of the strings str1, str2, str3, ... .
- 2 x y (1 ≤ x ≤ n) where y is a string, consisting of lowercase English letters. Change the string at position x to y.

Input format:
The first line of input contains 2 integers n and q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) – The number of strings and the number of queries, respectively.

The second line contains n strings stri consisting of lowercase English letters.

The next q lines describe the queries and may have one of the 2 forms:

- 1 a b (1 ≤ a ≤ b ≤ n).
- 2 x y (1 ≤ x ≤ n), where y is a string consisting of lowercase English letters.

the total length of all strings in input won't exceed 105

Output format:
For each query of first type output its answer in a new line.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
5 9
mahmoud mahmoudbadawy drmahmoud drevil mahmoud
1 1 5
1 1 2
1 2 3
2 3 mahmoud
2 4 mahmoud
2 2 mahmouu
1 1 5
1 2 3
1 1 1

Example output:
14
14
13
30
12
7

Editorial:
First, Let's get rid of the LCP part.
**observation:** $${ L C P ( s t r _ { 1 }, s t r _ { 2 }, \ldots, s t r _ { k } ) = \operatorname* { m i n } _ { i = 1 } ^ { k - 1 } L C P ( s t r _ { i }, s t r _ { i + 1 } ) }$$, That could make us transform the LCP part into a minimization part by making an array lcp where lcpi = LCP(si, si + 1), You could calculate it naively, And when an update happens at index a, You should update lcpa (If exists) and lcpa - 1 (If exists) naively.
Now the problem reduces to finding a ≤ l ≤ r ≤ b that maximizes the value:-
$$(\min_{i=l}^{r-1} lcp_i) * (r - l + 1)$$, If we have a histogram where the ith column has height lcpi, The the size of the largest rectangle that fits in the columns from l to r - 1 is $$(\min_{i=l}^{r-1} lcp_i) * (r - l)$$, That's close to our formula not the same but it's not a problem (You'll see how to fix it later), so to get rid of finding the l and r part, We can make that histogram and the answer for a query will be the largest rectangle in the subhistogram that contains the columns from a to b - 1, One of the ways to solve it is to try some heights h and see the maximum width we can achieve if h was the height, call it w, and maximize with h * w, To solve the slight difference in formulas problem we'll just maximize with h * (w + 1)!!
Let BU be a value the we'll choose later, We have 2 cases for our largest rectangle's height h, It could be either h ≤ BU or h > BU, We will solve both problems separately.
For h ≤ BU we can maintain BU segment trees, Segment tree number i has 1 at index x if lcpx ≥ i and 0 otherwise, When we query, It should get us the longest subsegment of ones in the query range, Let's see what we need for our merging operation, If we want the answer for the longest subsegment of ones in a range [l;r], Let mid = (l + r) / 2, Then the answer is the maximum between the answer of [l;mid], The answer of [mid + 1;r], And the maximum suffix of ones in the range [l;mid] added to the maximum prefix of ones in the range [mid + 1;r] . So we need to keep all these information in our node and also the length of the interval, As it's a well-known problem I won't get into more detail. Back to our problem, We can loop over all h ≤ BU, Let the answer for the query on range [a;b - 1] in segment tree number h be w, The maximum width of a rectangle of height h in this range is w and we'll maximize our answer with h * (w + 1).
For h > BU, Let's call a column of height greater than BU big, The heights we'll try are the heights of the big columns in the range, We don't have to try all the heights greater the BU, There are at most $${\frac {tot}{BU}}$$ big columns (Where tot is the total length of strings in input), Let's keep them in a set, When an update happens, You should add the column to the set or remove it depending on its new height, The set's size can't exceed $${\frac {tot}{BU}}$$ now, Let's see how to answer a query, Let's loop over the big columns in range [a;b - 1] only, If 2 of them aren't consecutive then the column after the first can't be big and the column before the second either, That's because if it were big, It would be in our set, So we can use this observation by making a new histogram with the big columns in the range only, And put a column with height 0 between any non-consecutive two, And get the largest rectangle in this histogram by the stack way for example in $${\cal O}\left(\frac{tot}{BU}\right)$$, The stack way will get us the maximum width w we can achieve for a rectangle containing column number i, We'll maximize with lcpi * (w + 1).
Also the answer for our main formula can be an interval of length one, All what I mentioned doesn't cover this, You should maintain another segment tree that gets the maximum length of a string in a range for this.
Maximize all what we got, You have the answer, Now it's time to choose BU, It's optimal in time to choose BU near $${ \sqrt { \frac { t o t } { \log { t o t } } } }$$ but that's not possible because of the memory limit so you have to choose a smaller value, 75 would be good, With some optimizations you can raise it up.
**Optimization:** The longest subsegment of ones problem is solved by BU segment trees and each one has 4 integers in each node, You can make them 2 integers (max prefix and suffix of ones) and make another only one segment tree that has the rest of the integers, That would divide the memory by 2 letting you choose bigger BU and consume less time.
Time complexity : O(tot + q(BU * log(tot) + tot / BU))
Thanks to [user:gritukan,2017-09-18] for making it harder and more interesting.
Solution link ([user:gritukan,2017-09-18]) : TODO.
Solution link ([user:mahmoudbadawy,2017-09-17]) : TODO.