Блог пользователя toilanvd_HSGS

Автор toilanvd_HSGS, 10 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you! I think it will work efficiently.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just brute force using bitmask?