Original Post: https://jiry-2.blog.uoj.ac/blog/1404
The following content is translated by Gemini 2.5 Pro.
Part 1: Introduction to the Hacking Method
How to Map the Hack Sequence to a Segment Tree
First, we are given a Hack sequence of length $$$len$$$. After $$$O(1)$$$ range addition operations and $$$\Theta(\log len)$$$ global $$$\text{chkmax}$$$ operations, this sequence becomes a cyclic shift (rotation) of the original sequence. Since a cyclic shift does not affect our range addition and global $$$\text{chkmax}$$$ operations (we can simply shift the indices for the range addition accordingly), we can consider the sequence as unchanged.
If we have such a sequence, let $$$len=n^{\frac{1}{3}}$$$, and place such a sequence at intervals of $$$n^{\frac{2}{3}}$$$. Each sequence corresponds exactly to a segment tree interval. A subtree of size $$$n^{\frac{2}{3}}$$$ contains exactly one such segment tree interval.
For the Hack sequence, the range addition operations are performed one by one on each interval, but the $$$\text{chkmax}$$$ operation can be executed for all of them with a single global instruction. That is, one $$$\text{chkmax}$$$ operation can recurse down to these $$$n^{\frac{1}{3}}$$$ Hack intervals, accessing at least $$$\Omega(n^{\frac{1}{3}}\log n)$$$ segment tree nodes each time. Since the $$$\text{chkmax}$$$ operation is performed uniformly $$$\log len=\log n$$$ times, the total number of accessed nodes is $$$\Omega(n^{\frac{1}{3}}\log^2 n)$$$.
The total number of range addition and global $$$\text{chkmax}$$$ operations is $$$O(n^{\frac{1}{3}}+\log n)=O(n^{\frac{1}{3}})$$$. Dividing the number of accessed nodes by the number of queries (operations), we get the average number of nodes accessed per operation as $$$\dfrac{\Omega(n^{\frac{1}{3}}\log^2 n)}{O(n^{\frac{1}{3}})}=\Omega(\log^2 n)$$$.
Construction of the Hack Sequence
The code can be found in Tony2's generator or negiizhao's revised version.
In my generator, vf[n] stores a Hack sequence of length $$$\text{Fib}_{2n+1}$$$, where $$$\text{Fib}_0=0, \text{Fib}_1=1$$$.
Translating the code into steps: 1. For an $$$n$$$-th order Hack sequence, first subtract $$$\text{Fib}_{2n-1}$$$ from the first $$$\text{Fib}_{2n}$$$ numbers. 2. Add $$$\text{Fib}_{2n}$$$ to the last $$$\text{Fib}_{2n-1}$$$ numbers. 3. Perform a global $$$\text{chkmax}$$$ with $$$\text{Fib}_{2n}$$$ (this will affect $$$n$$$ distinct values, meaning it can actually be decomposed into $$$n$$$ $$$\text{chkmax}$$$ operations, $$$n-1$$$ of which merge the minimum and second minimum values, triggering the access condition of the original algorithm). 4. Change the $$$\text{Fib}_{2n}$$$-th number to $$$0$$$.
We find that the sequence now becomes exactly the original sequence cyclically shifted to the right $$$\text{Fib}_{2n}$$$ times.
We know that $$$\log\text{Fib}_{2n+1}=O(n)$$$, so the number of effective $$$\text{chkmax}$$$ operations in this process indeed reaches $$$\Theta(\log len)$$$ (where $$$len=\text{Fib}_{2n+1}$$$), while there are only $$$O(1)$$$ range addition and point modification operations. This meets the requirements for a Hack sequence.
The construction method can be seen in the code. As for why this construction yields these properties, I didn't find the sequence directly at the beginning; it was derived from a structure.
If you don't want to read further, you can directly look at an example for $$$n=3$$$.
19 16 17 16 8 14 11 12 11 8 9 8 0
Add $$$8$$$ to the last $$$5$$$ numbers, and subtract $$$5$$$ from the first $$$8$$$ numbers.
14 11 12 11 3 9 6 7 19 16 17 16 8
Perform a global $$$\text{chkmax}$$$ with $$$8$$$. This step is actually performed sequentially on $$$3,6,7,8$$$. The middle two steps will reduce the number of distinct values.
14 11 12 11 8 9 8 8 19 16 17 16 8
Change the $$$8$$$-th number to $$$0$$$.
14 11 12 11 8 9 8 0 19 16 17 16 8
For convenience, cyclically shift right by $$$5$$$ positions.
19 16 17 16 8 14 11 12 11 8 9 8 0
The sequence remains unchanged, so the hack is successful.
Part 2: What is the Structure / How was it Found
Define two structures $$$f_n,g_n$$$. Define two sequences $$$a_n,b_n$$$.
Definition of $$$a,b$$$:
$$$a_0=b_0=0$$$
$$$a_1=b_1=1$$$
$$$b_n=a_{n-1}+b_{n-1},a_n=a_{n-1}+b_n$$$
We find that, in fact, $$$a_n=\text{Fib}_{2n},b_N=\text{Fib}_{2n-1}$$$.
Definition of $$$f,g$$$:
$$$f_0=g_0={(0,1,0)}$$$
$$$f_n={(0,a_n+b_n,0)}\ \cup\ add(f_{n-1},(0,a_n+b_n))\ \cup\ add(g_{n-1},(b_n,a_n))$$$
$$$g_n=f_n\ \cup\ add(g_{n-1},(a_n+b_n,0))$$$
Here, the triplet $$$(x_1,x_2,y)$$$ represents a line segment from $$$(x_1,y)\sim (x_2,y)$$$. The operation $$$add(S,(\Delta x,\Delta y))={(x_1+\Delta x,x_2+\Delta x,y+\Delta y)|(x_1,x_2,y)\in S}$$$.
First, we need to understand the line segments as an $$$f$$$-type node in a tree. Each $$$f_n$$$ creates an $$$n_f$$$ node, whose left child is an $$$(n-1)_f$$$ node and right child is an $$$(n-1)_g$$$ node. As for $$$g_n$$$, it creates an $$$n_g$$$ node whose left child is an $$$n_f$$$ node and right child is an $$$(n-1)_g$$$ node.
Note that here $$$n_f,n_g$$$ is just a classification, representing a type of node. A tree can have many $$$n_f$$$ nodes.
This process of alternating iteration generates a tree. Assuming the root of the tree is $$$n_f$$$, let's first observe some properties of this tree.
The root $$$n_f$$$ corresponds to the node $$$(0,\text{Fib}_{2n+1},0)$$$.
$$$a_n+b_n=a_n+(a_{n-1}+b_{n-1})$$$. This means that the y-coordinate of the line segments corresponding to the root of the left child of $$$n_f$$$ and the root of the left child of the right child of $$$n_f$$$ are the same.
$$$a_n=a_{n-1}+b_n$$$. This formula will be useful later.
Any node in the tree clearly corresponds to an x-interval $$$[l,r]$$$.
Next comes the most crucial part: splitting the tree into two parts and reassembling it. We split the tree at $$$x=a_n+0.5=\text{Fib}_{2n}+0.5$$$, which means deleting all nodes satisfying $$$l\le x \lt r$$$. The deleted nodes can be either $$$f$$$ nodes or $$$g$$$ nodes.
A miracle occurs: after the deletion, the left side of the tree forms the shape of a new $$$(n-1)_g$$$ node on the plane. The right side of the tree forms an incomplete $$$f_{n-1}$$$ node, missing some line segments. We try to complete it: the first segment to add is at $$$y=a_n-a_{n-1}=b_n,x_1=a_n,x_2=a_n+b_n$$$. The subsequent segments all satisfy $$$x_1=a_n$$$, which is precisely the cutting position. The position of the next segment is easy to find: at $$$y=a_n+b_{n-1}=a_n+a_{n-1}-a_{n-2}$$$.
The left part of the tree is easy to understand. Since $$$(n-1)_f,(n-2)_f,...$$$, are left, these nodes naturally form an $$$(n-1)_g$$$ node. This is actually because $$$n_g$$$ is $$$n_f+n-1_f+...+0_f$$$, which can be easily derived from the recurrence relation. So these $$$(n-1)_f,(n-2)_f,...$$$ will form $$$(n-1)_g,(n-2)_g,...$$$ through a suffix sum.
Why are the manually added line segments on the right side of the tree valid? In fact, when $$$n_f$$$ is deleted, what remains is the right child of the right child of $$$n_f$$$: $$$(n-2)_g$$$. The next remaining node is $$$(n-3)_g$$$. The difference in their y-coordinates is $$$a_n+a_{n-1}-a_n=a_{n-1}=b_{n-1}+a_{n-2}$$$. Why split it into $$$b_{n-1}+a_{n-2}$$$? This indicates that if we insert an $$$(n-2)_f$$$ node between these two nodes at this time, its right child would be exactly $$$(n-3)_g$$$, and the y-difference would be $$$a_{n-2}$$$; its parent should be $$$(n-1)_f$$$, and the y-difference between the root of the parent's right child and left child would be exactly $$$b_{n-1}$$$. This perfectly satisfies the structure of the initial construction. Ultimately, we only need to balance the two sides of the tree (subtract $$$b_n$$$ from the left side, because the root should be at $$$y=a_n$$$; add $$$a_n$$$ to the right side, because the root should be at $$$y=a_n+b_n$$$), swap them left and right, and then add back the original $$$(0,a_n+b_n,0)$$$ to get the initial tree.
Next, I will draw the case for $$$n=3$$$ in GeoGebra.
This is the structure of $$$3_f$$$. Each line segment represents the root of an $$$f$$$-type node. The $$$g$$$-type nodes are hidden; for example, $$$(5,13,8),(10,13,8),(12,13,8)$$$ are the roots of a $$$2_g,1_g,0_g$$$ node, respectively.
When the tree is cut, we find that the left side is completely a $$$2_g$$$ structure. Although $$$(0,8,13)$$$ was not a node before, we can now set it as a node.
After deleting the segments cut by the green line, we add back three red segments. This way, $$$x=8$$$ and its right side form a $$$2_f$$$ structure with $$$(8,13,5)$$$ as its root.
After that, by swapping the left and right sides and translating them vertically, we get back the original structure.
Now we embed the Hack sequence into this structure. For any $$$n_g$$$ node, we get a point $$$(x,y)$$$ at its left endpoint, which means the $$$x$$$-th term of the sequence is $$$y$$$. Let's mark this idea on the $$$n=3$$$ case.
The red dots represent the points in the sequence. When we cut along the green line, something interesting happens: $$$(5,13),(7,13),(8,13)$$$ should become new red dots, because a $$$2_g$$$ has appeared here. But the original red dots were at $$$(5,8),(7,11),(8,12)$$$. We need to perform a $$$\text{chkmax}$$$ operation with $$$13$$$ on these three positions to get the correct result. This is exactly what we want to hack: the operation becomes a $$$\text{chkmax}$$$ on the range $$$[1,8]$$$ with the value $$$13$$$. With a simple adjustment, this becomes a global $$$\text{chkmax}$$$ operation. The left-right swap of the structure is not actually performed, so the entire sequence is cyclically shifted to the right by $$$a_n$$$ positions. The point $$$(5,8)$$$ in the figure does not appear after the shift, but we only need to make $$$(13,0)$$$ a red dot as well to satisfy the condition.
So how was this structure found? This traces back to a long history of theoretical deduction. First, our model is to perform range addition and global $$$\text{chkmax}$$$ operations on a sequence. Since we need to analyze all sequences, we can only retain the properties of the sequence that are preserved after these operations. For example, after a $$$\text{chkmax}$$$ operation, we know for sure that all values that were chkmax'd become the same, and the remaining values are definitely larger. So we can use these size relationships to build a Cartesian tree (or forest). Why a forest? Because range addition operations (actually suffix additions) will break some size relationships, causing the Cartesian tree to split.
Here, after a long period of deduction, I did not arrive at a proof. So I turned to the theory of "disintegration pairs" to predict the change in the "number of distinct values". (This is because a $$$\text{chkmax}$$$ operation only reduces the "number of distinct values" by one at a time. If we can make this value grow quickly and yet be able to reduce it many times with $$$\text{chkmax}$$$ operations, then we can successfully hack it.) The definition of a disintegration pair is: suppose there is a pair of positions $$$(p_1,p_2)$$$ whose values will remain the same after a certain $$$\text{chkmax}$$$ operation, until a range addition operation breaks this property. A disintegration pair appears at the moment that makes their Cartesian tree the same, which is when $$$(p_1,p_2)$$$ belong to the same Cartesian tree until being separated by that one range addition. This moment should obviously be a $$$\text{chkmax}$$$ operation, but this is meaningless, because as long as one $$$\text{chkmax}$$$ operation is performed, all trees will be merged. So we might as well say it is created by rejoining after a split caused by a range addition.
So the lifecycle of a disintegration pair is as follows: it is created after a range addition causes the Cartesian tree to split, its two positions' values are confirmed to be equal by a $$$\text{chkmax}$$$ operation, and finally, a range addition operation kills this disintegration pair. It takes three steps in total, which we will call step one, step two, and step three. A disintegration pair is in state $$$1$$$ from step one to step two, and in state $$$2$$$ thereafter.
Observation reveals that disintegration pairs form a tree-like relationship. Step one is actually adding a state $$$1$$$ chain. Step two turns some disintegration pairs into state $$$2$$$, and the values of these pairs are actually the same, meaning an invisible "shackle" is created. The purpose of this shackle is to prevent the originally equal-valued disintegration pairs from being split during step one (i.e., when adding a state $$$1$$$ chain). This means these shackle-controlled pairs need to be within the children of the same node before being split by a range addition (of course, the shackle will split into two after being cut in the middle). Step three is to delete a state $$$2$$$ chain starting from the root.
Since the concept of shackles in the above observation was too abstract, I turned to rephrasing the problem as constraining each $$$\text{chkmax}$$$ operation to turn some state $$$1$$$ disintegration pairs $$$(p_1,p_2),(p_2,p_3),...,(p_{k-1},p_k)$$$ into state $$$2$$$ and be controlled under one shackle. This is effectively adding a new node on top of these pairs to prevent them from being separated.
The final breakthrough was an observation: the state $$$1$$$ chain added in each first step must be colored into state $$$2$$$ from top to bottom, and it must follow the order of color, delete, color, delete. This led us to represent this state $$$1$$$ chain directly as a node, just a node with many children, one of which is deleted at a time. The guarantee of state $$$2$$$ comes precisely from the aforementioned "shackle" nodes. At this point, a model emerged: the tree has some shackle nodes and original nodes. Let's call them square nodes and circle nodes. We might as well dictate that under a circle node must be square nodes, and under a square node must be circle nodes. Step one is to create a circle node, which can take several square node roots as its children. Step two is to create a square node, which can take several circle node roots as its children. Step three is to delete a square-circle chain, but actually only deleting the edges within it. This clearly reminds us of the disjoint set union (DSU) single path compression model: deleting edges in the middle of a chain and merging them under one node is exactly what path compression does. The only difference here is that the model has circle and square nodes.
After getting this model, I was very confident that Segment Beats could be hacked. The next thing I did was to study the method of hacking DSU with single path compression using binomial heaps and apply it to this problem. In the analysis above, the roots of $$$f$$$ are actually disintegration pairs. The chain of $$$f$$$'s going leftwards represents a model of a circle node with multiple children. The $$$f$$$ nodes within a $$$g$$$ structure (except for the last one, which is more of an auxiliary node) are the shackled ones. That is, the $$$f$$$ nodes whose two sides are guaranteed to be identical by $$$g$$$ are the state $$$2$$$ disintegration pairs. The rest are in state $$$1$$$. The splitting operation described above is precisely for killing some disintegration pairs and creating new ones. So, disintegration pairs are the edges in the circle-square tree, and the line segments in the $$$f,g$$$ system. These things are basically equivalent.
Finally, after referring to the DSU with single path compression hack, I designed this recursive construction model. The only problem I encountered was what values to fill in for $$$a,b$$$. Fortunately, after analyzing the properties of both sides, this sequence could be solved. In the end, they are both Fibonacci sequences.
Part 3: Miscellaneous Talk
The Segment tree beats algorithm was proposed by jry in 2016. I can't seem to find the ppt I saw when I first learned this thing, but I remember it had a background of AngelBeats!. I was very new to this back then and didn't even try to understand the time complexity.
Until 11.13 I saw some people in the u group discussing this problem, and I began to think about it. My first step was to think about the properties of the change in the "number of distinct values" (or "colors") of a sequence. I tried to characterize the change in the future curve of the number of colors for a sequence, which transformed the problem into one about permutations, but I immediately ran into difficulties.
About a day or two later, I thought about the idea of building a Cartesian tree forest for the sequence. But at that time, this Cartesian tree didn't consider 1 2 size relationships, so the number of roots would change abruptly with range additions, i.e., cutting the tree. I was stuck again for a while.
Another day or two passed, and I came up with the complete Cartesian tree. Now the change in the number of roots became reasonable, but the chkmax operation still caused strange changes to the tree's structure. I tried to build a structure similar to a circle-square tree to directly analyze the changes in the number of various points, but found this to be futile, as a lot of information was linearly dependent.
Then I discovered that I could use "disintegration pairs" to predict the future disintegration of pairs of identical colors. When two trees merge, some disintegration pairs are created; when they split, some are removed. The chkmax operation can make some disintegration pairs truly become pairs of identical numbers. These three operations became the foundation of my subsequent research. At that time, I gave a pseudo-proof while retaining only two of the operations.
After this flawed proof was published, some people tried to understand it. With the help of critno, I found the loophole in the proof, and the proof collapsed. After a long time of failed attempts at patching it up, I tried to find a hack. I found a line of thought for a hack, similar in structure to DSU, but then I realized I had missed the property that chkmax operations would "merge" disintegration pairs, and the hack exploded.
Thus began a long period of struggle. With the help of the "merge" property, the whole structure seemed invulnerable. At the same time, there were as many as three operations; removing any one of them or any one property would directly lead to a wrong hack. In the middle, I pondered questions like "what kind of 1 3 steps are valid for 2 step" and "is there a model where the number of operations, including confirmation and deletion, is reduced after adding a chain?", but couldn't find a reasonable explanation.
The final crack was opened by a property: a chain of disintegration pairs added in a single instance must be colored and deleted from top to bottom. The model was corrected to a DSU model similar to a circle-square tree, and I could immediately see the hope for a hack. It was around these few days that I learned the method for hacking DSU with single path compression and applied it to this problem. After a day of muddled thinking due to general physics homework, I finally found a structure very close to the hack on 12.23.
I was very excited that day because I felt I was very close to the finish line. Creating the structure, filling in the various values, solving the recurrence relations for the values, and finally obtaining the beautiful structure that performs range addition at the 0.618 point. This time it wouldn't be false again; the 1log proof would no longer exist.
By now, some people should have understood this hack, but it might be difficult to understand how this hack came about. I had to draw many diagrams on scratch paper to explain the principle of the hack to my roommate zxb. The content on the scratch paper has been written in the images above.
Finally, I want to thank all the friends who were willing to listen to my crazy pseudo-proofs at the beginning and everyone who has ever tried to prove or hack this problem. It is my honor to be the one to finally achieve this hack.
