「MXOI Round 2」队列

Luogu

IDLGP9588

Time1000ms

Memory512MB

DifficultyP4

线段树倍增二分平衡树树状数组单调队列洛谷原创O2优化优先队列前缀和队列洛谷月赛

小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下： $1\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\cdots,x$； $2\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素； $3\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素； $4$：这是第四种操作，表示查询队列中所有元素的最大值。你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。 ## Input 第一行两个整数 $c,q$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。接下来 $q$ 行，每行 $1 \sim 2$ 个整数，表示一个操作，格式见【**题目描述**】。 ## Output 对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。 [samples] ## Note #### 【样例解释 #1】在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$。在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$。 #### 【样例 #2】见附加文件中的 `queue/queue2.in` 与 `queue/queue2.ans`。该样例满足测试点 $1$ 的限制。 #### 【样例 #3】见附加文件中的 `queue/queue3.in` 与 `queue/queue3.ans`。该样例满足测试点 $4$ 的限制。 #### 【样例 #4】见附加文件中的 `queue/queue4.in` 与 `queue/queue4.ans`。该样例满足测试点 $11$ 的限制。 #### 【样例 #5】见附加文件中的 `queue/queue5.in` 与 `queue/queue5.ans`。该样例满足测试点 $15$ 的限制。 #### 【样例 #6】见附加文件中的 `queue/queue6.in` 与 `queue/queue6.ans`。该样例满足测试点 $20$ 的限制。 #### 【数据范围】设 $\sum x$ 表示单个测试点内 $x$ 之和。对于 $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$。 |测试点编号|$q \le$|$x \le$|$\sum x \le$|特殊性质| |:---:|:---:|:---:|:---:|:---:| |$1\sim3$|$500$|$500$|$2\times10^5$|C| |$4\sim8$|$5000$|$5000$|$2\times10^7$|无| |$9\sim10$|$2\times10^5$|$10^9$|$2\times10^{14}$|AB| |$11\sim12$|$2\times10^5$|$10^9$|$2\times10^{14}$|B| |$13\sim14$|$2\times10^5$|$10^9$|$2\times10^9$|AC| |$15\sim16$|$2\times10^5$|$10^9$|$2\times10^9$|C| |$17\sim18$|$2\times10^5$|$500$|$2\times10^7$|无| |$19$|$2\times10^5$|$10^9$|$2\times10^9$|无| |$20$|$2\times10^5$|$10^9$|$2\times10^{14}$|无| 特殊性质 A：没有第二种操作。特殊性质 B：没有第三种操作。特殊性质 C：没有第四种操作。

Samples

Input #1

Output #1

API Response (JSON)

{
  "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你需要帮助他维护这个队列，并...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments