I invent method to merge two cartesian trees with maybe intersect keys. And want to know what is asymptotic of it.
method:
let's add to a standard cartesian tree field musorka
struct Node {
Node *l = NULL, *r = NULL;
int key, priority, cnt = 1;
Node *musorka = NULL;
}
and when we want to merge trees A and B A->musorka = B
then write push
void push(Node *node) {
if (!node->musorka) return;
push(node->l);
push(node->r);
pair<Node*, Node*> spl = split(node->musorka, node->key);
pair<Node*, Node*> spl2 = split(spl.second, node->key + 1);
if (spl2.first) {
node->cnt++;
}
node->l->musorka = spl.first;
node->r->musorka = spl2.second;
node->musorka = NULL;
}
then add this push to merge and split.
Maybe someone can estimate asimptotic of this or give counter test where it works n^2?
Have you tried running it on random cases?
I was solved the problem:
given array 1, 2, 3, .., n you need to move elements from [l, l + k) to [r, r + k)
example:
[1], [2, 3], [13], [8], [5], [6], [7] let l = 1, r = 5, k = 2 result should be [1], [], [], [8], [5], [3, 6, 2], [7, 13]
I wrote this structure and it passed system test, but author's solution is different
After h (the height of the tree) merges to the same tree, all the nodes'
musorkawould be non-null.In this case, each successive merge would have to traverse
nnodes.You can't merge same tree multiple times.
What do you mean? My understanding is that if you have 3 trees, A, B, and C, you merge them by doing
A->musorka = B; A->push(); A->musorka = C; A->push();(Typing on mobile is freaking hard ><)
But then what's the problem?
Eventually all the nodes (musorka) in A would be full.
Why?
I think A nodes would be full if we merge to A trees with size of A
If I understood and implemented the idea correctly, I'm sorry to disappoint you, but the idea TLEs on 702F - Футболки. The problem basically can be solved with the thing you described (if it worked fast enough). Here is a link to my submission.
PS: This obviously is not a proof but at least might help in finding a counter sample.
PS2: It seems that the main reason why it TLEs is because a long path in the treap is created (the number of times "push" is called isn't large). This happens, because the above algorithm breaks the "heap" ordering by priority. Currently I'm trying to fix this, so I'll update this comment in about an hour.
PS3: I did a couple of optimizations but still couldn't fit the problem in 4 sec. Best I could achieve was AC with 20 sec on max test (I created a mashup with a different TL).
PS4: I managed to pass the problem with the same idea, but done in a different way. Here is the submission.
PS5: The same idea passes also for 911G - Запросы на массовое обновление. You can check a cleaner implementation here. The merge without the constraints is "merge_op".
Try rnd() % (a->sz + b->sz) < a->sz in merge, not a->prior < b->prior
Well with this way of merging it still TLEd. But it did manage to get AC on the first 60 tests. I'll try some constant optimizations to see if I can make it fit.
Submission
I have passed this task(T-Shirts) in 655 ms, submission — https://codeforces.net/contest/702/submission/46662757.
I do same things as mentioned in the blog, but without temporary
musorka. I think a musorka is useless because we postpone a merge operation that we must do in the future and we don't get any time profit.That looks like an amortization of naive merge: instead of splitting the second tree at the time of operation at all points at once, you postpone that until the data is really needed. I suspect that some simple potential method should be sufficient to proof the bound.
After some discussion with ifsmirnov it looks like amortized O(log2n) for each merge/split operation for me. Unfortunately, I don't have a rigid proof. The hand-waving goes like this: let's assume that we have an implicit segment tree instead of treap (the one which doesn't create a node unless there is a value in the corresponding subtree). That's somewhat worse than treap because it adds extra vertexes/levels, although structure may be different from treap. Afterwards, it looks like this post may help.
Another idea about constructing a bad test (I suspect that it will be O(n·log2n)): let's start with an array of 0... 2k - 1 sorted by reversed binary representations of numbers (e.g. 0, 4, 2, 6, 1, 5, 3, 7). Now let's merge adjacent elements and get {0, 4}, {2, 6}, {1, 5}, {3, 7}. Now let's merge adjacent elements as well and get {0, 2, 4, 6}, {1, 3, 5, 7}. And again, until we get a full tree. The idea is to always merge very "interleaved" trees.