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
Link to problem Spoj
Is there any other approach to it ?
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)).
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 block
I dont think there is someway to update it faster than log N . Please see my code !!
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))).
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
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 decomp
Segtree + Trie (TLE)
Treap + Trie (TLE)
TLE sqrt decomp
Are you talking about Mo's algorithm ? What have you done ? I think your solution is quite close to mine!
I do not know dude , when I change my block size to 1005 my code gets AC -_- !!
And I didnt even knew that it is a standard type of algorithm known as "SQuare root decomposition"
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
you can use it anywhere but i dont think its ever expected
Can you show me a good problem in which you've used it and got AC :P
I know 1, if u are still interested.
Yes please
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).
And another 1: http://acm.timus.ru/problem.aspx?num=1390&locale=en
If u will need some hints PM me, otherwise i might not notice.
Same happened with me. Changing block size to 1000 from 500 worked. I have analyzed the complexity. This is why it worked
For 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 works
Edit: Corrected my mistake.
I believe O(1009) makes no sence btw
Oh Sorry My bad. It was 500*log(500) so O(5000) for the 500 block and O(3500) for the 1000 block.
i mean you dont use O() like that, it has to have some function of N inside brackets. at least i believe in it
I think there exists some better algorithm for this task seeing multiple solutions with very small running time
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)
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
My implementation. Sqrt-Decomposition + BIT. Time : 1.1 Seconds (before they changed the processors). 0.8 seconds on Cube.
And how did you know if its cube or pyramid or anything else? Where's this written?
it's written under the time limit
I wrote many solutions and I got two of them accepted:
Nested Trie
Trie + sqrt(n) decomp