You are not logged in. Please login at www.codechef.com to post your questions!

×

ZQUERY(SPOJ)

Can anyone tell me the suitable algorithm/approach to solve this problem http://www.spoj.com/problems/ZQUERY/

asked 05 Oct '14, 19:52

viperx's gravatar image

4★viperx
3114
accept rate: 0%

edited 05 Oct '14, 19:54


I think this can be solved by sqrt decomposition in O(Q * M * log(N)) time where M = sqrt(N). The basic idea is to divide the given array into M blocks each of size M, Now we change each element a[i] to its prefix sum. Then a sum of range l...r is zero if and only if a[l - 1] == a[r]. Now each query range l...r can be covered by at most M blocks of size M and at most 2*M-2 trailing and leading elements. For each distinct element we can store all its occurrences at separate places and we can to binary search to find the right most elements which is less than or equal to r. Similarly we can do for each block we pre-process and store what is the answer for each right in O(N) so total of O(N * M) for M blocks and answer in O(1) for query on each block. And I also guess that we can remove the log(N) factor of binary search by doing offline programming.

link

answered 16 Nov '14, 01:17

adurysk's gravatar image

5★adurysk ♦
92852428
accept rate: 11%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,100

question asked: 05 Oct '14, 19:52

question was seen: 4,481 times

last updated: 16 Nov '14, 01:17

Related questions