sa +president_tree + brute_force Accepted this problem, seems it is O(n*poly(log(n)),but it needs some proof...,there is litte possibilaty it is O(n^2*poly(log(n))).
# | User | Rating |
---|---|---|
1 | tourist | 3803 |
2 | jiangly | 3707 |
3 | Benq | 3627 |
4 | ecnerwala | 3584 |
5 | orzdevinwang | 3573 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | Radewoosh | 3542 |
9 | jqdai0815 | 3532 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 165 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | maroonrk | 152 |
5 | -is-this-fft- | 151 |
5 | nor | 151 |
7 | atcoder_official | 147 |
8 | TheScrasse | 146 |
9 | Petr | 145 |
10 | SecondThread | 142 |
sa +president_tree + brute_force Accepted this problem, seems it is O(n*poly(log(n)),but it needs some proof...,there is litte possibilaty it is O(n^2*poly(log(n))).
Name |
---|
president_tree ?? I`m missed smth definitely interesting.
My approach is very brute_force,and it is an online algorithm:
First build suffix array and lcp[], for each query [li,ri],lets find the nearest right rank of position (lm=li), in the position,interval [li+1,ri],we denote this positon,pos,then find lcp=lcp[li][pos], then lm=max(pos, ri-lcp+1), in order to speed up to find the first yes postion, we must deal with parttern str=AAAAAAAA+prefix(A) (this is not legal answer,but currenc lcp value is max.),A is a string,if this pattern is occur we directly get pos=max(pos,len(str)-len(A))..
with this speed up we can get the first yes positon (pos+lcp>ri) we only jump log(n) times, but this is not the final answer, this is a lcp_max() answer but not the left most answer, so we must continue to go left, denote lm=max(lm,ri-lcp+1),rm=min(rm,sa[pos]-1), similarly there may occur str=AAAAAAA+prefix(A) (this is a legal answer), we can binary_search to find the left most legal answer (jump lenth(A) positon),and denote rm with this left most legal postion.
this is an online algorithm and I have test for each query the maximum iteration times is not exceed 40, so maybe this is an O(q*Log(n)^log(n)) algorithm...
and seems editorial is an offline parralell binary search approach, this is interesting.