The order of queries and the order in which rungs are crossed are different. Query order determines which rungs exist for each question, while height order determines how those rungs are crossed. Read the entire input first and handle these two orders separately.
Let be the number of type queries, and number them in their input order. If type queries have appeared before a rung is added, that rung exists only for questions with numbers at least . Store each rung as its left line , height , and threshold . If , there are no answers to output, so processing of this test case can end.
Think of each question as a ball placed on its starting vertical line. For each line , maintain a set of the question numbers currently on that line. Initially, put the number of each question into .
Sort all rungs by increasing height and process them from top to bottom. For a rung , exchange only the elements numbered at least between and . Questions numbered below must remain unchanged because this rung had not yet been added when those questions were asked. Rungs at the same height share no vertical line, so they can be processed in any order.
To perform these exchanges efficiently, represent each set by a dynamic segment tree over the coordinate interval . Create leaves containing question numbers and their ancestors as needed. Every line's tree uses the same subdivision of this interval, so entire subtrees representing the same interval can be exchanged.
To exchange the interval between two trees, suppose the current pair of nodes represents :
If both trees are empty, return immediately. If only part of the interval must be exchanged and one node is missing, create an empty node on that side to hold its two children. Exchanging node references does not copy a subtree.
At each depth, at most one interval contains the threshold in its interior. Every other interval is either left unchanged or exchanged as one whole subtree. Thus, processing one rung takes time and creates at most that many new nodes.
After processing all rungs, traverse the tree for each line . For every question number found at a leaf of that tree, set . Output these answers in question number order.
Let be the number of rungs, so . Building the initial trees takes time, sorting the rungs takes , and processing all exchanges takes . Including initialization of the line roots and the final tree traversal, the total time complexity is . Counting all nodes created during initialization and exchanges gives the same bound, , for space.
Proof
Fix a question number and a rung. If questions have appeared before that rung is added, questions with occur before its insertion, and questions with occur afterward. Hence, this rung exists for question exactly when .
Solution written by GPT6
While processing rungs in height order, maintain the following invariant: each question number belongs to the set of the line reached in that question's ladder after descending through all heights processed so far. Initially, every question is on its starting line, so the invariant holds.
Consider a rung . If , the rung does not exist for question , and its position must stay unchanged. If , it must cross to the other side exactly when it is currently on line or ; otherwise, it stays where it is. Exchanging the elements numbered at least between these two sets performs precisely these moves. The segment tree recursion exchanges exactly the leaves in that interval, so it implements the same operation. The invariant is therefore preserved.
Rungs at the same height use disjoint pairs of vertical lines, so their processing order does not affect the result. After all rungs have been processed, each question has passed every rung present in its ladder, from top to bottom. By the invariant, the line whose set contains that question is its actual destination. Consequently, every output answer is correct.
