Hello,

During the last educational round I had a solution with treaps for which I cannot construct a sample to make it TLE. It seems to me that the solution is or something like that but I cannot prove it. So can someone either provide a counter sample or help me prove it. Thanks in advance!

Here is a link to the submission.

I think it should pass. Worst case happens when you are doing query in sequences like this — "12121212..121", and changing 1'

sto 2's. I mean too many intersections. But once you change all 1'sto 2's, then next time there will be a large range of 2's, which is good. And if you transform 1 to something else then that will be just , as the while loop will run only once.So, I think the while loop runs

O(n) over all queries. So it is overall.I don't think you can simply say that this is the worst case... Obviously many intersections is bad, but in the case when you have just 1's and 2's the problem becomes much easier — just store intervals of consecutive equal values, because changing 1 to 2 on some interval is the same as setting everything to 2. This is not true in the general case though.

If you take the case when you have lots of intersections, but there are many different values, I don't think you can analyze it this easily — you could try to look at each pair of values separately, but then you would get a big constant like

AorA^{2}(whereAis the number of different values) in the complexity. I'm also unable to prove it but I think the complexity of this approach is subquadratic independent ofA(so it solves a more general problem).https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/replace-27c5286c/ . This is a harder version of problem G. Also the editorial explains the complexity. My implementation http://codeforces.com/contest/911/submission/33747581 .

As far as I read, the editorial didn't actually explain the complexity of their solution. It uses a different approach (persistent segment trees instead of treaps) but in general has the same idea / problem: efficiently merging two nonempty nodes from the two different trees. Their approach is to call merge two times recursively — separately on the two left and the two right children of our nodes.

The editorial says that this algorithm had complexity but it doesn't explain why splitting the recursion doesn't impact overall complexity.

To me it seems like the number of splits the recursion does would depend on

n. If that were the case, the complexity would have to be something greater than .You can prove an amortized bound.

For a BST

A= (a_{1}, ...,a_{k}) define the potential . The total potential is just the sum of Φ over all trees.If you split

Abetweena_{j}anda_{j + 1}, you loose the term , the potential doesn't increase, hence the amortized time is .If you concatenate two trees

A,B(your 'merge' function), you get an additional term which is at most , so the amortized time is .When merging two trees

A,B(your 'while(mid)' loop), the resulting tree's in-order will consist of blocks contains onlyas or onlybs. The number of loop iterations is linear in the number of blocks. (I think it's around half the number of blocks.) Let's look at a non-boundary block ofb's.and the potential

(We get the as every block boundary is considered in an

ablock and abblock.)Note that

b_{j}<b_{l}, soby Jensen's inequality for . Hence the potential decreases by at least for every non-boundary block. This amortizes the -worst case time of stuff we do inside the loop. The boundary blocks increase the potential by at most , so the amortized runtime is .

Since the sum in Φ(

A) contains term which all are , the initial potential is at most . Hence the total runtime is amortized .I think you can get by using finger search trees.

I may have misunderstood something, but not every block boundary is considered in both an

aand abblock.Let's say that we're merging two trees

A= (0, 8) andB= (4). Let's denote the tree we get after the merge withC= (0, 4, 8).Before the merge we have Φ (

A) =lg(n)·lg(8 - 0) =lg(n)·lg(8) = 3·lg(n) and Φ(B) = 0. The total potential is Φ_{1}= 3·lg(n). After the merge we have Φ(C) =lg(n)·(lg(4 - 0) +lg(8 - 4)) =lg(n)·(lg(4) +lg(4)) =lg(n)·(2 + 2) = 4·lg(n) .The total potential didn't decrease by

lg(n) — it even increased.Also, what's the purpose of the

lg(n) term before the sum? I mean, doesn't it always stay there, so it's basically a constant ?The first and last block boundaries are the ones that are not considered twice. Their contribution is at most .

We need the factor to amortize the time (from BBST split/concat operations) of a single loop iteration, as the parts only give us a decrease of 1 per iteration.

PS: You can type

`\lg`

to get nicer .My bad, I didn't see that you had addressed my concern a few sentences later. So your proof seems to be correct.

I meant that you can define your potential as Φ(

A) =lg(a_{2}-a_{1}) +lg(a_{3}-a_{2}) + ... +lg(a_{k}-a_{k - 1}). Then it will be an upper bound of the number of merges the`while(mid)`

loop does, each requiringO(lg(n)). Again you will get an overall complexity ofO(n·lg(n) +q·lg^{2}(n)).And I was aware of but while "nicer", it displays as an image and not as text. When

Unable to parse markup [type=CF_TEX]

is rendered as an image it sometimes doesn't display when I click "preview" (at least in my browser). I didn't want to use an externalUnable to parse markup [type=CF_TEX]

editor, so i stuck to just usinglg().