python - Equal elements in SubArray -


i have array containing n elements , need find distance between index of equal elements in subarray; in form of query (l r) l starting index of subarray , r in ending index. total no. of array elements can n<=10^5 , queries q<=10^5.

ex:

7  0 4 0 8 0 32 0  2  0 2  0 5 

//answer 1st query 2 (index 2-0)

//answer 2nd query 8 (index (2-0) + (4-2) + (4-0))

edit: not expecting code (though helpful) general idea solve great help.

this job sqrt decomposition.

we want maintain state allows answer current range , adjust endpoints of current range or down one. end, maintain map element (sum of indexes of element in current range, number of occurrences in current range). maintain current answer. adjust lower endpoint down include element x @ index i, increment answer sum of indexes in range - (#occurrences of x in range * i), increment sum , number of occurrences. other 3 operations similar.

to achieve sqrt decomposition, sort queries (lower endpoint floor divided sqrt n, upper endpoint) , adjust range in order.


Comments

Popular posts from this blog

c++ - Difference between pre and post decrement in recursive function argument -

php - Nothing but 'run(); ' when browsing to my local project, how do I fix this? -

php - How can I echo out this array? -