Badry's blog

a nice problem on data structures
By Badry, history, 8 years ago, In English

Hi codeforces, I need to solve this sub task " given an array of zeros we need to apply 2 types of operations on it 1- increment elements in a given range by 1 or decrement them by -1 .. 2- count the number of positive integers in the array " I have a solution which work in O(M*sqrtN*logN) where M is the number of operations. but this solution is not fast enough to pass the time limit .. could some one please give me a faster solution. thanks in advance

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

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Badry (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have a idea which may help you to drop the 'logN'.

First, divide the sequence into sqrtN blocks, each with sqrtN size. In each blocks, sort them and compressed the same value into a pair (v, cnt). By maintaining a ptr in each block to the least number which is larger than 0, you can easily tell how many positive numbers in each block, then the whole array.

For some 'partially changes' may happen, you should use 'merge sort' like algorithm to rearrange the partially changed blocks in O(sqrtN) time.

Totally, a O(M * sqrtN) algorithm?

I think you can hardly do it in O(N poly(logN))...

→ Reply