We have got N number, from 1 to N. There are 2 types of query:
- move number from index i to index j
- write what number is at index i
ex.
(0,1,2,3,4);
2 ? -> 2
(0,1,3,4,2); <- from 2 to 4
(0,4,1,3,2); <- from 3 to 1
3 ? -> 3
4 ? -> 2
(0,4,1,3,2); <- from 1 to 1
0 ? -> 0
1 ? -> 4
2 < N < 10 000 000 M < 500 000
I tried with the sqrt-decomposition but not fast enough.. any ideas? http://cms.di.unipi.it/#/task/vasi2/statement
this problem can be solved using bit or segment tree. can u share link to the problem so that I can test my idea and then discuss wid u.
If M is the number of queries you could try coordinate compression: instead of keeping track of all numbers keep track of those that appear in the queries.
Assume that we have N numbers from 1 to N.
Can you send a link to the problem? The difficulty of this problem depends on the time and memory limits.
I solved this problem using a modified AVL tree.
I've tried to solve the problem using an AVL tree like a list, with log N insertion, deletion, and find k-th item. The main problem is that I spend so much time by populating the tree with the initial number from 0 to N-1, so it's TLE.. suggestions?
Do you build the tree in O(N) or O(N*logN) time?
O(N), the build function is like:
Focus on the fact that you don't actually need to erase and insert nodes in each update...
You mean when the two positions are the same?
Does the tree size change after an update? If no, is it necessary to delete and allocate nodes during updates?
The size of the tree does not change .. I don't know how to do an update without remove a node and re-insert it in the right position. Is it possible?
It is necessary to remove and insert nodes but you don't need to dynamically allocate them.
are you saying that i can create a static array of nodes of fixed size, and use only this space for the nodes? The heap dynamic allocations are "time dangerous"?
You call N times the function "new" or "malloc" to build the tree, instead if you use a static array you allocate memory only once.
now I'll try
I continue to receive TLE.. probably is something else c.c
edit. 100/100. I balance the tree only when the difference between the height of the child is more than 5.
The link for the problem is http://cms.di.unipi.it/#/task/vasi2/statement . The description is in italian
I think some straightforward-like solution with a BST might do well. The only improvement (O((M + N)logN) → O(MlogM)) I can think of is to store not single elements but ranges of consecutive elements. For example, in the very beginning you have a BST with only one node which represents the range 1... N. While updating you find the range which has the i-th element and split it into no more than three (that is, you delete it and insert several new).
Treap