### CarlaZZ's blog

By CarlaZZ, history, 7 years ago,

We have got N number, from 1 to N. There are 2 types of query:

1. move number from index i to index j
2. 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

• 0

 » 7 years ago, # |   0 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.
 » 7 years ago, # |   +5 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.
•  » » 7 years ago, # ^ |   0 Assume that we have N numbers from 1 to N.
•  » » » 7 years ago, # ^ |   +8 Can you send a link to the problem? The difficulty of this problem depends on the time and memory limits.
 » 7 years ago, # |   0 I solved this problem using a modified AVL tree.
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   0 Do you build the tree in O(N) or O(N*logN) time?
•  » » » » 7 years ago, # ^ |   0 O(N), the build function is like:  Node* construct(int s, int d) { if ( s > d ) return NULL; int mid = (s+d)/2; Node* new_node = new Node(); new_node->id = mid; new_node->left = construct(s, mid-1); new_node->right = construct(mid+1, d); new_node->size = size_node(new_node->left) + size_node(new_node->right) + 1; new_node->height = max(height(new_node->left), height(new_node->right)) + 1; return new_node; } 
•  » » » » » 7 years ago, # ^ |   0 Focus on the fact that you don't actually need to erase and insert nodes in each update...
•  » » » » » » 7 years ago, # ^ |   0 You mean when the two positions are the same?
•  » » » » » » » 7 years ago, # ^ |   0 Does the tree size change after an update? If no, is it necessary to delete and allocate nodes during updates?
•  » » » » » » » » 7 years ago, # ^ |   0 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?
•  » » » » » » » » » 7 years ago, # ^ |   0 It is necessary to remove and insert nodes but you don't need to dynamically allocate them.
•  » » » » » » » » » 7 years ago, # ^ |   0 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"?
•  » » » » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 now I'll try
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 I continue to receive TLE.. probably is something else c.cedit. 100/100. I balance the tree only when the difference between the height of the child is more than 5.
 » 7 years ago, # |   0 The link for the problem is http://cms.di.unipi.it/#/task/vasi2/statement . The description is in italian
 » 7 years ago, # |   +10 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).
 » 4 years ago, # |   0 Implicit treaps can be used to solve the problem. For referernce https://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-2
 » 4 years ago, # |   0 Treap