BaoBao the Witch is stuck in a maze with nnn rows and nnn columns, where the height of the cell in the iii-th row and the jjj-th column is hi,jh_{i,j}hi,j. To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down. More formally, you need to find a sequence (x1,y1),(x2,y2),⋯ ,(xn2,yn2)(x_1, y_1), (x_2, y_2), cdots, (x_{n^2}, y_{n^2})(x1,y1),(x2,y2),⋯,(xn2,yn2) such that: For all 1≤i≤n21 le i le n^21≤i≤n2, 1≤xi,yi≤n 1 le x_i, y_i le n1≤xi,yi≤n; For all 1≤i,j≤n2,i≠j1 le i, j le n^2, i neq j1≤i,j≤n2,i=j, (xi,yi)≠(xj,yj) (x_i, y_i) neq (x_j, y_j)(xi,yi)=(xj,yj); For all 2≤i≤n22 le i le n^22≤i≤n2, ∣xi−xi−1∣+∣yi−yi−1∣=1|x_i - x_{i-1}| + |y_i - y_{i-1}| = 1∣xi−xi−1∣+∣yi−yi−1∣=1; ∑i=2n2[hxi−1,yi−1
标签： HBC236059[SHOI2009]会场预约 线段树 STL 伸展树Splay 数据结构So I'll Max Out My Constructive Algor...题解
