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

a nice problem on data structures
Автор Badry, история, 8 лет назад, По-английски

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

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

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

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить