P5313 [Ynoi2011] WBLT

The time was probably around the subject summer camp period. Back then, several other students in the informatics group, as well as some new 11th graders, had started learning splay. Every day I heard zms and yjq (a senior student, very strong) discussing splay, and they even jokingly called it "spaly". It made me feel nervous: how could they be learning something so hard while I still knew nothing about it? Then I searched for splay online. I saw several hundred lines of code, things like zig, zag, potential analysis (so why do such ugly blogs rank so high), and felt that this thing was impossible to understand. I skimmed it but did not understand anything. I went to ask what splay could do. The answer was: "insert, delete, query the $k$-th smallest". Anyway, I was bored every day, so I thought about it. A segment tree can query the $k$-th smallest, as long as its leaves are sorted. So can a segment tree do it too? But our segment tree is a static structure (that was my thinking at the time). It has to become dynamic, otherwise how can we insert and delete? A segment tree maintains the interval of each node, which is static. That is the core problem, so we consider how to make it dynamic. When inserting a node, if we find the insertion position, it must be a leaf. We can create two new leaf children for this node. We can see that all nodes after this insertion position are shifted. So we can consider using a tag to maintain this, called a shift tag. Each time we `push_down` the shift tag to achieve dynamization. When deleting, we can use its sibling to replace the deleted node. Similarly, we need to maintain the shift tag. When querying, first `push_down` the shift tag, then decide whether to go into the left child. We can see that this structure will have complexity problems under chain-like insertion data, so we consider how to balance it. The first thing I thought of was setting a ratio so that the proportion of left and right subtrees stays within the ratio; otherwise, we rebuild by brute force. I wrote it and it seemed correct, then I asked Yu-shen, and he said this is a "Scapegoat Tree"... So I invented a balanced tree myself? In that case, balanced trees are quite simple. In that case, I am very strong (an illusion). Then I kept thinking along this line and came up with many strange implementations, such as merging when unbalanced, or splitting by midpoint, and so on. I wrote a random strategy and passed the balanced tree template problem, but it was very complex at the time because I maintained the parent pointer and the implementation was not optimized. Later I found that the so-called shift tag was not needed. We can directly maintain `size`, so we can binary search downward by relative position, reducing a lot of code. I also found that we do not need to store `father`, reducing a lot of code. I further found that this tree can also be "rotated". We can define rotation as merging two nodes (so whenever I see claims like "rotationless treap does not need rotation, unlike treap", I feel quite speechless, because it is essentially an equivalent operation. It is the same thing, just written differently). It can also be split. Here I defined splitting as performing $O( logn )$ rotations so that the right child of the root's left child becomes the interval we need. I found that the balanced tree I designed can indeed support all operations, the complexity is also $O( logn )$, and personally I think it is very easy to write. So I invented a balanced tree? At that time I gave it a name, "Self Balancing Segment Tree". Later, after searching for a long time, I found that it was actually a combination of two things that were not introduced into the OI community. It should be called "Weight Balanced Leafy Tree". When I first made it, I thought it was very important, so I hid it from others, afraid that my classmates would learn my technique. I also knew that there were only 5 spots in the provincial team, and my classmates were my competitors. At that time, mhy heard that my balanced tree was very strong and asked whether I could write it in 10 minutes. I accepted the challenge, and I actually wrote it out, earning +1 recognition from the CTT seniors. At that time I was full of confidence. If I could invent such a strong data structure, then getting into the CTT and being recommended to Tsinghua or Peking University would be easy (a flag). [Remember to add an illustration, for WBLT.] Since this is Ynoi, not a place for the problem setter to write show-off text, you need to solve a data structure problem.

You are given a sequence of length $n$, with $m$ query operations. Each query gives parameters $l,r,b$. You need to output the maximum $x$ such that there exists an $a$ with $0\leq a

The first line contains an integer $n$. The second line contains $n$ integers representing the sequence. The third line contains an integer $m$. Then follow $m$ lines, each containing three integers $l,r,b$, representing one query operation.

For each query operation, output one line with one integer representing the answer.

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078&Forever_Pursuit. For $30\%$ of the testdata, all numbers that appear are within $[0,1000]$. For another $30\%$ of the testdata, $b \leq 1000$. For $100\%$ of the testdata, all numbers that appear are within $[0,10^5]$. Translated by ChatGPT 5