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!
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).
Thank you! I think it will work efficiently.
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.
Just brute force using bitmask?