### anh1l1ator's blog

By anh1l1ator, 4 years ago, ,

So , formally the problem statement :

You are given a sequence A of N (N≤250000) integers between 1 and 50000. On this sequence you have to apply M (M≤10000) operations of the form: modify the i-th element in the sequence and then say how many inversions are there in the sequence. The number of inversions in a sequence is given by the number of pairs (i,j) with i < j and Ai > Aj.

My approach is to , 1) Divide the array into square root pieces , and maintain a fenwick tree for each of the blocks that stores 1 corresponding to each number in that block ( For querying number of numbers lesser than a particular value in that block )

2) Count the inversions .

3) Now whenever Update comes , I update get inversions from all blocks except the index's box(I count the difference between the inversions due to the new value — inversions due to old value and add it to the inversions) and add it ! Plus I traverse the block of index ! Total Query time O( Sqquare root of N * log 50000 ) .

It is giving TLE Even with fast scanning and outputting Here is my code , can it be further optimised ? Ideone

Is there any other approach to it ?

• +4

 » 4 years ago, # |   +1 For each query you should find: in how many inversions i-th number participed before and new number of inversions for updated number.Total number of inversions will change for difference of this two number. So you should count in each query how many numbers are bigger left of a[i] and how many numbers are smaller right of a[i]. You can do this in sqrt(n)-easy dp. Dp[i][j] count the number of smaller numbers than j in i-th block.After query update dp for block where is placed i-th number. Total complexity O( n sqrt(n)).
•  » » 4 years ago, # ^ |   0 To update DP[i][j] after each update it will take j operations where j can be at max 50000. Now to speed up this procedure I have used a series of fenwick trees (for each square root block a different one ) which can cause fast retrieval and fast updation but the problem is it is timing out!! As your state is Dp[i][j] count the number of smaller numbers than j in i-th blockI dont think there is someway to update it faster than log N . Please see my code !!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 My bad, you are right ( I see three ziroes in max number, not four :D ). I can make it a little better ( maybe):You can sort all the blocks and after that to find number of values bigger and smaller than a[i] in every block you can run binary search. Complexity of that program is O(m sqrt(n) log (sqrt(n))).
•  » » » » 4 years ago, # ^ |   0 Happens with everyone :D And I will try it once I get AC , coz I dont think there is much difference as the maximum value of elements is lesser than max of N . Plus BIT doesn't have a big constant
 » 4 years ago, # |   +6 I recently solved this problem using sqrt decomposition , i got TLE first when i had block size as 500 , but then i tried some other things like trie + treap / trie + segtree , all TLEd then finally i went back to sqrt decomposition and kept block size as 1000 and added fast input and it gave AC . Final AC code with sqrt decompSegtree + Trie (TLE)Treap + Trie (TLE)TLE sqrt decomp
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Are you talking about Mo's algorithm ? What have you done ? I think your solution is quite close to mine!
•  » » » 4 years ago, # ^ |   0 I do not know dude , when I change my block size to 1005 my code gets AC -_- !!
•  » » » » 4 years ago, # ^ |   0 And I didnt even knew that it is a standard type of algorithm known as "SQuare root decomposition"
•  » » 4 years ago, # ^ |   0 Do you know of a problem in which the expected solution involves a Treap + Trie or a Segment Tree with a Treap for each node? I'd really like to solve such a question :P
•  » » » 4 years ago, # ^ |   0 you can use it anywhere but i dont think its ever expected
•  » » » » 4 years ago, # ^ |   0 Can you show me a good problem in which you've used it and got AC :P
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I know 1, if u are still interested.
•  » » » » » » 3 years ago, # ^ |   0 Yes please
•  » » » » » » » 3 years ago, # ^ |   +5 http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=111142. THe statement is in russian, but the rough trasnlation is:Shooting gallery. U have 3D space and N shooting marks in it, which are rectangles, parallel to x0y plane and Z meters away from it. (U shoot from x0y plane). All Z[i] are different.Then u have M queries, each query is: given 2D point on the x0y plane, meaning that shoot is happening from this point. When u shoot bullet moves perpendicular to x0y plane towards increasing z. When it hits a mark bullet stops and mark falls.For each shoot task is to output number of mark it hits or 0, if it doesnt hit any1.Queryes are happening one by one, previos queryes DO affect marks obviously(i mean, if any mark falls after some query, its not used anymore).
•  » » » » » » » 3 years ago, # ^ |   +5 And another 1: http://acm.timus.ru/problem.aspx?num=1390&locale=en
•  » » » » » » » 3 years ago, # ^ |   +5 If u will need some hints PM me, otherwise i might not notice.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Same happened with me. Changing block size to 1000 from 500 worked. I have analyzed the complexity. This is why it workedFor each query, For 500 block size complexity= O(500+ 500 * log(500))=O(5000) For 1000 block size complexity= O(1000+ 250 *log(1000))=O(3500)Therefore 1000 worksEdit: Corrected my mistake.
•  » » » 3 years ago, # ^ |   +11 I believe O(1009) makes no sence btw
•  » » » » 3 years ago, # ^ |   0 Oh Sorry My bad. It was 500*log(500) so O(5000) for the 500 block and O(3500) for the 1000 block.
•  » » » » » 3 years ago, # ^ |   +13 i mean you dont use O() like that, it has to have some function of N inside brackets. at least i believe in it
•  » » » » » 3 years ago, # ^ |   0 I think there exists some better algorithm for this task seeing multiple solutions with very small running time
 » 3 years ago, # |   +6 you can use segment tree with an ordered multiset(also you can compress numbers first and use fenwick that is faster) on each node. so we can answere each query in O(lg(n)^2)
•  » » 3 years ago, # ^ |   +3 Yeah this is a very easy solution , I probably didn't ever knew anything as segment tree with sets that's why i wrote such a bad solution :D
 » 3 years ago, # | ← Rev. 3 →   0 My implementation. Sqrt-Decomposition + BIT. Time : 1.1 Seconds (before they changed the processors). 0.8 seconds on Cube.
•  » » 3 years ago, # ^ |   0 And how did you know if its cube or pyramid or anything else? Where's this written?
•  » » » 3 years ago, # ^ |   0 it's written under the time limit
 » 2 years ago, # |   0 I wrote many solutions and I got two of them accepted:Nested TrieTrie + sqrt(n) decomp