1232 : 数据结构假象
时间限制Time Limit
2
秒Sec
内存限制Memory Limit
256
兆MB
提交次数Submitted
4
次Times
通过次数Solved
1
次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
点击可查看各语言的读写示例。 Click for I/O samples in each language.
题目描述Description
给定一个长度为 \(n\) 的序列 \(a\) 和数字 \(k\),你需要支持 \(m\) 次操作或查询:
\(\text{C t}\):将最大的数字减去 \(k\)(如果有多个,则选择最左边的数字),此动作反复执行 \(t\) 次。
\(\text{A x}\):询问序列中第 \(x\) 大的数字。
输入格式Input
第一行包含三个整数 \(n\)、\(m\) 和 \(k\) \((1\leq n,m\leq 5\times 10^5)\)。
接下来一行包含 \(n\) 个整数,表示序列 \(a\) \((1\leq a_i\leq 10^{18})\)。
接下来的 \(m\) 行中,每行包含一个字符和一个整数,表示一次操作或查询。
对于所有数据,保证 \(1\leq k,t\leq 10^{18}\),\(1\leq x\leq n\)。
保证每次操作后的序列对所有 \(a_i\) 都满足 \(-10^{18}\leq a_i\leq 10^{18}\)。
输出格式Output
对于每个查询,输出一个整数表示答案。
样例Sample
出题Author
SYSU