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

How to solve CPAIR(counting pairs) on SPOJ?
Автор vasandani68, история, 9 лет назад, По-английски

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

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

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

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Sorry for bringing the old post back !!! But Can someone please tell how to do the query ???? I understood the segment part and joining ,But How to do query?? Can someone please share their ideas ??? Thanks in advance.

        → Ответить