bablu_45's blog

By bablu_45, history, 5 days ago, In English,

We are given an array of size 'N' with 'Q' queries. Each query contains 3 integers (A,B and C) which divides the entire array into 4 parts or subarrays, [0,A-1],[A,B],[B+1,C] and [C+1,N-1]. We need to swap first and second subarray and third and fourth subarray.

You need to output the final array after Q queries.

Constraints:

1<=N<=10^5

1<=Q<=10^5

1<=A[i]<=10^9.

Eg:- N=9 with 2 queries

9 2

1 2 3 4 5 6 7 8 9

2 4 6

1 3 5

In first query we are supposed to swap [0,1] and [2,4], [5,6] and [7,8]. So after first query array becomes [3,4,5,1,2,8,9,6,7]

In second query we are supposed to swap [0,0] and [1,3], [4,5] and [6,8] of modified array. So final array is [4,5,1,3,9,6,7,2,8]

How to solve this question?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

You should read about treap, it can be used to solve this.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    treap-is-like-this-knife
    After seeing so many similar comments about treap, now I start imagining treap as a weapon like this. :D

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Treap is just easy to implement. You need to implement split, merge and a function to update nodes, all of them are at most 10-15 lines of code. With it you can make an array where you can access element, split it into parts and merge them in $$$O(\log n)$$$

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I heard treap can do many things. Xellos has mentioned some of them in his blog.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok, I will read about treaps and then give this question a try.

»
5 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Make a temporary array that will tell you final index of all the elements. For every query shift the elements from 0 to A-1 by A units(simply by adding +A at index -1 and -A at index A) and elements from A to B by -A units by a similar strategy. Do the same for B to N. When all the queries are over simply do a prefix sum calculation over this array. The final value will tell you the modified index.

  • »
    »
    5 days ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    I don't think it will work as the positions of every element changes after each query and for the next query we need to modify the elements/sub-arrays according to the new positions.