YoyOyoYOy000y000's blog

Xor subarray less than k in every query
By YoyOyoYOy000y000, history, 5 years ago, In English

you will be given an array. and q query. q and n all less than 100000.

In every query you will be given a k. how many subarray xor less than k?

** I think it can be solved by persistent trie. but i need another solution.

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Lets rephrase the problem a little bit. Denote by P[i] the XOR of numbers a[1], a[2], ..., a[i]. Now the XOR of subarray [L, R] becomes P[R] XOR P[L — 1] and the problem boils down to finding how many pairs of numbers from a list, when XOR-ed give a number less than K. This problem can be solved in O(NlogN) with the help of the Walsh-Hadamard transform and you can get some insight for the implementation from here: https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    i only know fast walsh hadamard gives us... all pairs xor/and/or sum. i don't know about this variation. Thanks.

    → Reply