I know I'm having discriminated against, please don't give me a downvote, at least read the entire blog completely first.
Everyone knows that the priority queue for C++ is log n, but this is very slow, so we hope to optimize it.
Some people believe that using vjudgian theorem can help you optimize to $$$O(-1)$$$. But this is wrong. The definition of complexity is $$$O(f(x))$$$ representation, and you can find an $$$f(x)$$$ and two cons
tants $$$c_1,c_2$$$ with true run time $$$g(x)$$$ such that $$$\text{lim}_{x→\infty}\text{ }c_1f(x)\le g(x)\le c_2f(x)$$$. So essentially $$$O(-1)=O(1)$$$. The Vjudgian theorem is very difficult and cannot be run on Codeforces testers, so I won't introduce this.
Let me present a method that can be run in Codeforecs and that can be easily coded by tourist and benq. First, go offline for the first time. Offline means that you can know in advance what all operations are and give the results of all queries at the last time. For priority queues, we believe that there are two operations: (inserting a number) and (accessing and popping a minimum).
For these two operations, we will convert them into a sequence, use — 1 for pop-up operations, and use the inserted integer for insert operations. For example, for $$$[11,12,-1,3,-1]$$$, we insert $$$11$$$, insert $$$12$$$, pop up a number, insert $$$3$$$, and pop up a number. Because this is offl
ine, we can handle this in any way we like. First, we will access all non $$$-1$$$ numbers from small to large. Any smart person knows how to do this within $$$O(n)$$$ using cardinality sorting.
Subsequently, for each accessed number, we find the $$$-1$$$ closest to it and on the right, and delete this $$$-1$$$. We can easily do this by using and searching the set.
But this is still not $$$O(n)$$$, but $$$O(nα(n))$$$ As a patient with obsessive compulsive disorder, I can't stand this.
So I took the dsu operation offline again. Create a graph that treats each dsu merge operation as an edge, and the edge weight is the order in which the operation is executed. Then perform a minimum spanning tree on the graph (Klein P N, Tarjan R E. A Randomized Linear Time Algorithm for Finding Minimum Sp
anning Trees [M]. Brown University, 1993).
Then only the edges on the minimum spanning tree is valuable, and then you discover that you can solve it using four Russian algorithms.
Cool. Downvoted.