So a few hours ago I was doing a problem which I will write here when I finish this short story. Now, I didn't have any idea of how to solve it, but then, I started thinking really hard, and found a CRAZY idea. I decided to call it fast, because this algorithm finishes even faster than you do (assuming you have someone to finish with).
So consider the following problem:
You are given a strictly increasing array a of size n and q queries, n, q <=2*10^5. There are 2 types of queries:
1 ind, val change the value of a[ind] to val, it is guaranteed that 1<ind<n, and a[ind-1]<val, and a[ind+1]>val.
2 val find the index where val appears.
Now in case you didn't notice, the array remains sorted after all queries. Now this is key.
I found a way to solve this problem in O(N+QlogN) using this algorithm:
For type 1 query we just update the array manually For type 2 query, we initialize l=1 and r=n. Next we check the element exaclty in the middle, and if it is bigger then the wanted value, then we know it's to the right of the wanted value, so we move r, because all the elements greater on indices greater than r are bigger than val. Now, we do the similar in symmetrical case. If the element is equal to val, then we found the index, and if l and r meet and we haven't fount it that means there is no elements val in the array. Now this alrogithm works in logN per query, because each iteration it cuts the search space in 2.
To end things off, I think this algorithm is really cool and overpowered, and I'm looking forward to problems containing it as the main solution. If anyone here wants to give me a CS degree for this great contribution to the CS world, I'm open to discussion.
I will here update the blog with the common questions:
LGMVasa, Thank you for your BIG... contribution to the CS world. And to that I answer, no problem!
LGMVasa, but I don't finish faster than this algorithm. Yes you do, don't lie to me.
zoves u kasne sate
trazis opijate
Uhm, well actually this problem can be solved in $$$O(n+q)$$$. So, well, we can deduce that we will never change an element into an already existing one. This means, erm, elements will always cease to exist and reappear. If a new element appears, another one will have to disappear. So we can have a, uhm, hash-map $$$h$$$ such that $$$h_{a_i} = i$$$.
We will first precompute the hash-map for the initial array. For queries of type $$$1$$$, erm, we will have to subtract 1 from $$$a_{ind}$$$ and add 1 to $$$val$$$. We will then turn $$$a_{ind}$$$ into $$$val$$$. This clearly works for every array. For queries of type $$$2$$$ we simply check if $$$h_{a_i} > 0$$$