hippie's blog

Interesting Array: tourist's code
By hippie, 10 years ago, In English

Problem --> Interesting Array (CF Round 275): Div.1/B or Div.2/D

Tourist's code : http://ideone.com/c5dTmY

In this problem, for every set bit in query, we set the corresponding bit for all the numbers in the given range. I can't understand how he's doing that by:

s[from[k]][j]++; s[to[k] + 1][j]--;

Also, for calculating the number of set bits for a given bit position, for a given range of numbers, he's made some sort of cumulative array. Please explain its construction:

bal += s[i][j]; a[i][j] = (bal > 0); sum[i + 1][j] = sum[i][j] + a[i][j];

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Each bit is an array in this matrix S, denoted by index j. Now lets just analyze one bit,so imagine your array is Arr = S[0..n][j]: when you assign a number X to an index, you say that, when you walk from left to right in the array, you'll have X added to each of the next positions. at the end of the interval, you add  - X to cancel off the effect of the first. So, at the end of the update, all you have to do is walk from left to right in O(n) steps and calculate each value in O(1) doing the subset sum of S.

→ Reply