|
|
My first attempt use string hashing to check the palindrome with Segment Tree lazy prop.
O(Q*K*logK*logN), esp. for the update query and it's TLE 11
However, using Manacher algorithm with Segment Tree you can achieve O(Q*(K+lgN))
Little help:
- WA#3 : You're likely answering too much. (K involved)
- WA#9 : N=10^5, overflow somewhere For anyone struggling with this problem, here's how I did it:
segment trees with lazy updates for the dp
O(sqrtN) updates for the string itself (the logN retrieval with the segment trees instead of the O(1) with the sqrt blocks retrieval was too big of a hog it seems, maybe I messed something up)
Manacher for the edge cases
and dp[i] = dpEven[i] + dpOdd[i] from Manacher
So I used the segment trees to do most of the work, and then for the edge cases I used Manacher, so on average I'd get O(sqrt(N) + log(N) + K) for updates and O(log(N) + K) for queries.
Does anyone have a less ugly solution? My source code is aroung 15kb (although I used long names for clarity) and around 550 lines long. Also I've seen people's code run a lot faster, under a second (mine ran in 2.7 s) and I was wondering how they did it. Thanks! rt TL 11 I did it with sqrt(N) blocks, and got tl on 11 too Can someone gives me algorithm or code ??? sabashavidze@gmail.com this is my gmail,thanks |
|
|
