T84081 [青五联考样板题] 快速排序

高考结束，各校展开了激烈的宣传之战。 “XX人数全OOO第一” “XXX创历史新高” “XX率领先全O”…… ------ 本题为青五联考样板题，另外三道样板题：[[青五联考样板题] 前缀和](https://www.luogu.org/problemnew/show/U75406)、[[青五联考样板题] 整除分块](https://www.luogu.org/problemnew/show/U74567)、[[青五联考样板题]快速数论变换](https://www.luogu.org/problemnew/show/U75643)。 ## 非常抱歉，之前的题目描述不清。为便于理解题意，题目描述中已增添如下文字：“如果按照上一条规则比较不出两所学校哪一所学校强，那么编号*小*的学校更强”。 ## 空间限制已放宽——MLE 会变成 TLE。

然而，作为 OIer 的 Shinko 并没有被宣传迷惑双眼。她决定按照 NOI 聚乙烯牌人数和 NOIP 省肆人数两个指标，给学校排名。 Shinko 认为，相比 NOIP 省肆人数，NOI 聚乙烯牌人数更能反映一个学校的实力；因此，应该这样比较两所学校： > 若甲乙两校的 NOI 聚乙烯牌人数相同，则 NOIP 省肆人数多的学校更强；否则 NOI 聚乙烯牌人数多的学校更强。 > 如果按照上一条规则比较不出两所学校哪一所学校强，那么编号**小**的学校更强。 例如： - 1 号学校的 NOI 聚乙烯牌人数为 $1$，NOIP 省肆人数为 $2$；2 号学校的 NOI 聚乙烯牌人数为 $2$，NOIP 省肆人数为 $1$。2 号学校比 1 号学校强。 - 3 号学校的 NOI 聚乙烯牌人数为 $2$，NOIP 省肆人数为 $2$；4 号学校的 NOI 聚乙烯牌人数为 $2$，NOIP 省肆人数为 $1$。3 号学校比 4 号学校强。 - 5 号学校的 NOI 聚乙烯牌人数为 $1$，NOIP 省肆人数为 $1$；6 号学校的 NOI 聚乙烯牌人数为 $1$，NOIP 省肆人数为 $1$。5 号学校比 6 号学校强。 现在 Shinko 交了很多的存储费、仓储费、出仓费、出场费、出厂费、出差费、出车费、车船费、乘车费、存车费、藏车费、铲车费、擦车费、叉车费、查车费、查重费、重测费、冲刺费、摧残费、吃醋费，才终于买到了 $n$ 所学校的数据。她想知道排第 $p$ 名的学校的编号。一个学校的排名定义为比这所学校强的学校数加 $1$。根据“强”的定义，每个排名唯一对应一所学校。 可是 Shinko 没有电脑，你能回答她的问题吗？毕竟，这会让她认识到，能帮她解决问题的学校才是最强的！ 由于 Shinko 是一个善于提问的好孩子，她的问题很多。为了节省你的时间，Shinko 决定把本题中涉及到的信息按照特殊的形式组织起来，具体见下面的“输入格式”。

本题输入格式特殊，请留意。 输入只有 $1$ 行，含有 $4$ 个正整数 $n,m,a_0,b_0$，$n$ 表示学校数，$m$ 表示 Shinko 的问题数，$a_0,b_0$ 的意义将会在下面叙述。 为得到 $n$ 所学校的数据，你需要调用 $2n$ 次 `next_school` 函数。每次调用的参数和返回值如下所述。 - 第一次调用 `next_school` 函数时，传入的参数是 $a_0$；此后每一次调用 `next_school` 函数，传入的参数是上一次调用 `next_school` 函数的返回值。 - 第 $2k-1,2k\ (1\le k\le n)$ 次调用 `next_school` 函数的返回值分别是编号为 $k$ 的学校的 NOI 聚乙烯牌人数和 NOIP 省肆人数。 为得到 Shinko 的 $m$ 个问题，你需要调用 $m$ 次 `next_query` 函数。每次调用的参数和返回值如下所述。 - 第一次调用 `next_query` 函数时，传入的参数是 $(b_0,n)$；此后每一次调用 `next_query` 函数，传入的参数是上一次调用 `next_query` 函数的返回值和 $n$。 - 第 $t\ (1\le t\le m)$ 次调用 `next_query` 函数的返回值是 Shinko 的第 $t$ 个问题，即题目描述中的 $p$。 提示与说明中有一个示例程序演示如何获得输入。 `next_school` 函数和 `next_query` 函数如下。 ```cpp inline unsigned next_school(unsigned x){ x^=x5,x^=x

输出共有 $m$ 行，每行一个正整数 $q$，表示排名为 $p$ 的学校编号。

对于 $10\%$ 的数据， $n,m\le 3$。 对于 $20\%$ 的数据， $n,m\le 10$。 对于 $40\%$ 的数据， $n\le 1000$。 对于 $70\%$ 的数据， $n\le 10^{5}$。 对于 $100\%$ 的数据，$1\le n \le 10^{7},\ 1\le m \le 750,1\le a_0,b_0 \le 10^9$。 ------ #### 样例解释 输入的 $20$ 所学校的 NOI 聚乙烯牌人数和 NOIP 省肆人数分别为： $$\begin{aligned}&(7081,8599), (3208,346), (9548,4054), (4826,1069), (5166,3726),\\&(4635,3552), (3793,4557), (3808,8168), (426,3810), (7001,7628),\\ &(5723,7388), (7701,2931), (9520,66), (7456,9840), (5967,7483),\\ &(881,9033), (5578,41), (4078,6415), (427,1745), (1998,4739)\end{aligned}$$ $8$ 个询问的 $p$ 分别是：$10,20,19,14,16,7,4,1$。 经过计算，得到的答案是：$5,9,19,8,2,15,14,3$。 ~~从这个样例，你知道哪所学校最强了么？~~ ------ #### 示例代码 ```cpp #include #define MAXN 10000005 using namespace std; int CH2CH2n[MAXN],fourth[MAXN],rank_i[MAXN]; unsigned next_school(unsigned x); unsigned next_query(unsigned x,int n); int main(void){ int n,m,a0,b0; cin >> n >> m >> a0 >> b0; for (int i=1;i