{"problem":{"name":"「MXOI Round 2」队列","description":{"content":"小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下： $1\\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\\cdots,x$； $2\\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素； $3\\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素； $4$：这是第四种操作，表示查询队列中所有元素的最大值。 你需要帮助他维护这个队列，并","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9588"},"statements":[{"statement_type":"Markdown","content":"小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下：\n\n$1\\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\\cdots,x$；\n\n$2\\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素；\n\n$3\\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素；\n\n$4$：这是第四种操作，表示查询队列中所有元素的最大值。\n\n你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。\n\n## Input\n\n第一行两个整数 $c,q$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。\n\n接下来 $q$ 行，每行 $1 \\sim 2$ 个整数，表示一个操作，格式见【**题目描述**】。\n\n## Output\n\n对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。\n\n[samples]\n\n## Note\n\n#### 【样例解释 #1】\n\n在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$。\n\n在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$。\n\n#### 【样例 #2】\n\n见附加文件中的 `queue/queue2.in` 与 `queue/queue2.ans`。\n\n该样例满足测试点 $1$ 的限制。\n\n#### 【样例 #3】\n\n见附加文件中的 `queue/queue3.in` 与 `queue/queue3.ans`。\n\n该样例满足测试点 $4$ 的限制。\n\n#### 【样例 #4】\n\n见附加文件中的 `queue/queue4.in` 与 `queue/queue4.ans`。\n\n该样例满足测试点 $11$ 的限制。\n\n#### 【样例 #5】\n\n见附加文件中的 `queue/queue5.in` 与 `queue/queue5.ans`。\n\n该样例满足测试点 $15$ 的限制。\n\n#### 【样例 #6】\n\n见附加文件中的 `queue/queue6.in` 与 `queue/queue6.ans`。\n\n该样例满足测试点 $20$ 的限制。\n\n#### 【数据范围】\n\n设 $\\sum x$ 表示单个测试点内 $x$ 之和。\n\n对于 $100\\%$ 的数据，$1 \\le q \\le 2\\times 10^5$，$1 \\le x,y,z \\le 10^9$，$0 \\le \\sum x \\le 2\\times10^{14}$，保证在进行第二种操作前队列内元素个数不小于 $y$，在进行第三种操作前队列内元素个数不小于 $z$，在进行第四种操作前队列内元素个数大于 $0$。\n\n|测试点编号|$q \\le$|$x \\le$|$\\sum x \\le$|特殊性质|\n|:---:|:---:|:---:|:---:|:---:|\n|$1\\sim3$|$500$|$500$|$2\\times10^5$|C|\n|$4\\sim8$|$5000$|$5000$|$2\\times10^7$|无|\n|$9\\sim10$|$2\\times10^5$|$10^9$|$2\\times10^{14}$|AB|\n|$11\\sim12$|$2\\times10^5$|$10^9$|$2\\times10^{14}$|B|\n|$13\\sim14$|$2\\times10^5$|$10^9$|$2\\times10^9$|AC|\n|$15\\sim16$|$2\\times10^5$|$10^9$|$2\\times10^9$|C|\n|$17\\sim18$|$2\\times10^5$|$500$|$2\\times10^7$|无|\n|$19$|$2\\times10^5$|$10^9$|$2\\times10^9$|无|\n|$20$|$2\\times10^5$|$10^9$|$2\\times10^{14}$|无|\n\n特殊性质 A：没有第二种操作。\n\n特殊性质 B：没有第三种操作。\n\n特殊性质 C：没有第四种操作。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9588","tags":["线段树","倍增","二分","平衡树","树状数组","单调队列","洛谷原创","O2优化","优先队列","前缀和","队列","洛谷月赛"],"sample_group":[["0 9\n1 5\n1 3\n2 2\n1 4\n3 6\n3 8\n2 4\n4\n3 3","3\n2\n4\n1"]],"created_at":"2026-03-03 11:09:25"}}