vasandani68's blog

How to solve CPAIR(counting pairs) on SPOJ?
By vasandani68, history, 10 years ago, In English

How can it be solved using Fenwick trees , DSU , Segment trees etc? Problem link- (http://www.spoj.com/problems/CPAIR/)

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

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

I solved this problem 2-3 weeks back I guess. Here is what I did:

I sorted the queries and numbers in decreasing order . Now keep DSU to keep the active segments and the segment size of each segment.

During a query you have to merge two segments and this will cause removal of two segments of some size and addition of a larger size subarray so you need a segment tree with lazy propagation for this. Each point in segment tree denotes the number of subarrays of size point index.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    can u explain in a bit naive way like what are active segments which u r taking about or actually what are the segments?

    if we take an 'i' then the possible 'j' which we can take are i+a,i+a+1,i+a+2,....i+b with the condition that all elements between i and j must be greater or equal to v.

    So what is the significance of sorting here and what are the segments which you are referring to?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Segments = Subarrays . Whenever you iterate on a query you will get many new subarrays and it is possible older subarray say [0,1] and [3,4] can be merged due to [2,2] element is bigger than the current query... Now the active segment will be [0,4] which is the merge of older two... Now the point on segment tree tells me that number of subarrays of size= index point... We can update on merging of two segments

      → Reply