silentboy302's blog

By silentboy302, history, 2 months ago, In English,

Problem: http://www.spoj.com/problems/IQUERY/

I think we can use segment tree for this problem. I figured out that the multiplication and addition part has the following property:
mul(i, j) = mul(i, k)+mul(k+1, j)+mul(i, k)*mul(k+1, j) where i <= k <= j.
So, this is easy to do with range trees.

But as bitwise and is not distributive over addition we can't define the second type of query as the previous one. Anyone approached the problem?

Any hint will be appreciated.

 
 
 
 

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by silentboy302 (previous revision, new revision, compare).

»
2 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

let's look for each bit separately. then i-th bit is contained in (2^(number of elements in the segment that have 1 in that bit) — 1 subsets)

so you need to keep log segment trees (in i-th segment tree you contain b[j] = (a[j] >> i) & 1, and then answer is sum(2^i*(2^sum(i-th segment tree, l, r) — 1)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. It was easy to verify that it should works.

    I will think at bit level from the next time if I stuck in any bit-wise issue.