How can it be solved using Fenwick trees , DSU , Segment trees etc? Problem link- (http://www.spoj.com/problems/CPAIR/)
# | User | Rating |
---|---|---|
1 | tourist | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 165 |
3 | adamant | 164 |
4 | TheScrasse | 159 |
5 | nor | 155 |
5 | maroonrk | 155 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
How can it be solved using Fenwick trees , DSU , Segment trees etc? Problem link- (http://www.spoj.com/problems/CPAIR/)
Name |
---|
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.
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?
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
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.
Why downvotes ??? Did I ask something wrong ???
Don't use a fake account to post comments.