mahmud2690's blog

By mahmud2690, history, 17 months ago, In English,

Hi, i am faced with the following 2D segment tree (actually title says) problem on SPOJ. Problem link here: link. Basically it says to find the area of union of rectangles. Number of rectangles is up to 10^5. Is it possible to solve this problem using 2D segment tree + lazy propagation?. I read about quadtrees, but it's written complexity of per operation in Quadtrees is O(N). Can you give any hint to solve this problem?

Read more »


By mahmud2690, history, 18 months ago, In English,

I am recently faced with the following problem. You are given binary string a and b where 1 <= length(a) <= length(b) <= 10^5. Let length(a) = n. Now we are required to find the smallest binary-valued substring S of b with length n where XOR(S, a) is minimum. I thought a solution with bitsets which may avoid TL, but i couldn't made it up. Can anybody help me to solve this, please?

Example: Input: 1101 1011000 Output: 1100

Read more »

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