1465: T2

题目描述

2022年2月4日，第24届冬季奥林匹克运动会在北京开幕。Kerbin星球上也在举行这冬奥会，不同的是，他们的冬奥会上有一个奇怪的项目。暂且不用关心这个项目比什么，更重要的是它的赛制规则。

有$n$名选手参赛，为了比赛正常进行，保证$n$是$2$的次幂($n=2^k$)。提供每一位选手的基本参赛信息，特别的，由于每一位选手都是身经百战的老手，很容易得知每个人的平均水平，我们用一个整数来评估。比赛开始前，$n$名选手按照给定的顺序依次排列，并且所有的选手被视作在同一小组比赛。接下来这个包含所有选手的小组开始比赛，参赛选手按照初始顺序相邻的两名选手展开比赛，其中获胜的选手进入优胜组，败北的选手进入劣汰组。在每个新产生的小组中，选手按照在原小组顺位的优先级排列，例如两个获胜的选手同时进入优胜组，原来小组里排在前面的选手在优胜组依然排在另一个选手之前。等上一轮的所有比赛结束之后，比赛轮数加$1$，特别的，规定比赛开始之前的轮数为$0$。下一轮的比赛在上一轮产生的所有小组中分别按照如上的规则进行。

为了方便理解，具体过程如上图所示，每一个小框代表一个小组，在一轮比赛之后分别产生两个新的小组。由于保证$n$是$2$的次幂，所以比赛能够一直进行下去。如果每次把获胜的小组排在淘汰的小组之前，最后会产生一个新的排序，作为最终排名。

小T是这项运动的爱好者，他收集到了这次冬奥会所有选手的参赛信息，平均水平和初始参赛排位。他想要在比赛之前按照选手的平均水平预估比赛结果。为方便预估，认为平均水平高的选手获胜(如果水平相同，排在靠前位置的选手获胜)。请给出最终的排名，如果选手人数超过$30$，则只要给出排名前$30$的名单。此外，小T会给出$q$个询问，每个询问包含两个选手编号(选手按照初始参赛排位编号，1-based)$x$和$y$($x$可能等于$y$)，请给出这两名选手最后一次分在同一小组是在第几轮比赛。

输入格式

第一行一个正整数$n$，参赛的选手数。

接下来$n$行，每行一个字符串包含一名选手的信息，其中姓名，国籍，年龄，平均水平以"_"隔开

具体参考样例输入，保证姓名和国籍只包含字母且长度分别不超过10，年龄和平均水平为不超过100的非负整数。

第$n+2$行一个正整数$q$，询问数。

接下来$q$行，每行两个整数$x$和$y$ ($1\le x,y\le n$)，表示询问的选手编号。

输出格式

前$\min(n,30)$行，每行一个字符串。

第$i$行表示排名为$i$的选手信息，格式为Rank xxx: name-xxx nation-xxx age-xxx，xxx填入内容，具体见样例输出。

接下来$q$行，每行一个整数，表示询问的两个选手最后一次同组的比赛轮数。

样例输入

```text 4 Alice_Germany_20_10 Bob_China_19_13 Carol_Norway_21_8 Dave_Sweden_22_15 3 1 2 1 3 1 4

```

样例输出

```text Rank 1: name-Dave nation-Sweden age-22 Rank 2: name-Bob nation-China age-19 Rank 3: name-Alice nation-Germany age-20 Rank 4: name-Carol nation-Norway age-21 0 1 0

```

数据范围

样例说明

第$0$轮排名：Alice, Bob, Carol, Dave
第$1$轮排名：Bob, Dave, Alice, Carol
第$2$轮排名：Dave, Bob, Alice, Carol
比赛结束

对于$20\%$的数据，$n=2^{11}$，$q=0$

对于另外$20\%$的数据，$n=2^{17}$，$q=0$

对于另外$20\%$的数据，$n=2^{17}$，$q=1$

对于另外$20\%$的数据，$n=2^{17}$，$q\le 10^5$

对于所有数据，$n=2^{17}$，$q\le 2\times10^6$

提醒

由于询问数$q$可能非常大，建议整数使用scanf和printf输入输出，避免io造成的超时。
如果要使用cin和cout，请在输入输出之前添加ios::sync_with_stdio(false);语句，并且用\n替换endl。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！