toilanvd_HSGS's blog

A problem with OR operation
By toilanvd_HSGS, 9 years ago, In English

I meet a hard problem with OR operation which I couldn't solve yet. However I think this one seem appeared in a round of Codeforces, I don't probably remember.

Given 2 strings with bit 0/1. String 1 has n bits, string 2 has m bits (n, m <= 10^5). There are at most 10000 queries, each contains 4 number a, b, c, d (condition is b-a=d-c). For each query, output one only number- numbers of bit 1 in the result when taking (segment [a,b] of string 1) OR (segment [c,d] of string 2).

Example:

n= 4, m= 5

String 1: 0011

String 2: 10101

Queries:

a= 2, b= 3, c= 1, d= 2 ----> answer is 2 because (01 | 10) = 11 which has 2 bit 1

a= 2, b= 4, c= 2, d= 4 ----> answer is 2 because (011 | 010) = 011 which has 2 bit 1

Thank you for reading!

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

»
9 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

For these constraints standard approach with bitmasks seems suitable( max(N, M)/32 for one query ). The number of queries is up to 10^4 so C++ bitset is likely to work fine(even if the number of queries would be up to 10^5).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! I think it will work efficiently.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      BTW, C++ bitset isn't fastest thing in the world, you may implement it by yourself — if you want faster solution :)

      If you don't like this solution for some reason — you can also solve it with FFT; check editorial of problem G from CF#270. In your problem answer for a query is equal to substring size minus number of 0-0 pairs.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just brute force using bitmask?

→ Reply