My sol involves suffix array and some count tricks.

first of all we initialization  [i,n-1] [0,i] is losing state, and the substring with same

oddity is losing state a different is winning state and count winning state +1 (it is a segment you can use fenwick tree to doit)

then we consider to enum the length of longest common substring, and merge the substring with longest common length of this length,if one of them is winning states ,then all of them are winning states.  how to merge them: using disjoint set, and how to find winning states  we can record substring [x,y] pref[x+y],win[x+y] as previous substring [l,r] with l+r==x+y and find this wining state by differece of odditiy of current substring and pref[x+y].  when merging them delete the node if it is not the root node, (i.e. do it count minus one count the all segments [l,r]  l-x==y-r with same oddity if it is win,different if it is lose. fenwick array can do it) and change the count when root node's winning states is update..


btw in fact we can throwout fenwick just using ordinary array and count sum of prefix of the array as number of its winning states.

I have heard there is O(N) rmq so this problem can be done in O(n)

btw there are many details on implement in my sol so I have spent nearly one week on this problem. maybe there are better sols...

Edited by author 30.09.2018 13:46

Edited by author 30.09.2018 14:01