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!