hars123's blog

By hars123, history, 6 years ago, In English

Substring Xor

Can someone explain me the detailed method about how to use tries and binary search to solve this problem.

  • Vote: I like it
  • -6
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's solve another problem: you are given an array, for each pair of indexes you compute a[j] ^ a[i] and you need to find the k-th element among computed values. You can find the solution here, problem F.

How, how to solve our problem? Let's compute auxiliary array b. b[j] = a[0] ^ a[1] ^ ... ^ a[j]. Notice that now we need to solve previous problem