Imosu是一位魔法少女,14岁时发现了魔法。
伊莫苏为了打败161天后到来的强敌“漏水”,正在训练增强自己的魔力。训练如下。 有
N 石头,每块石头都有确定的魔力值,排成一排。
如果你可以连续选择几块石头,并按照魔力升序重新排列,即将魔力较低的石头放置在数字较低的位置,则可以增加Imosu的魔力。所有石头都非常重,因此重新排列它们的唯一方法是使用魔法交换相邻的石头。
然而,石头太多,分类起来非常困难。有多种方法可以选择可以增加你的魔法力量的石头,所以你要选择最简单的一种。此外,石头的魔力强度会随着时间而改变。魔力强弱变化的方式,伊摩苏的魔法已经预见到了。
我希望你编写一个如下所示的程序来帮助 Imosu 进行魔法训练。
課題
N 整数数组 给出了 A 。从一排石头的左端开始 i+1 石头 i ,A[i] 是一块石头 让它代表 i 的神奇力量。
执行以下程序:
- 具有以下参数的过程 初始化(N,A):
- N -- 宝石数量。石头从左到右列出。 0 减去 N-1 它们用不同的整数编号,最大为 。
- A -- 代表石头魔法力量的整数数组。0 ≤ i < N 对于 反对 1 ≤ A[i] ≤ N 可以假设为 。
- 具有以下参数的过程 更新(i,x):
- i -- 魔力发生变化的石头数量。
- x -- 魔力变化后的石头 i 的魔力。1 ≤ x ≤ N 。
- 具有以下参数的过程 火车(p, q)
在调用:
- p -- 要排序的最左边的石头数量。0 ≤ p < N 。
- q -- 要排序的石头的最右边的编号。p ≤ q < N 。
例
N = 6,第一块石头的魔力状态为
| A = 考虑 | 4 |
| 1 | |
| 2 | |
| 2 | |
| 6 | |
| 5 |
的情况。
一、流程 初始化 使用上述参数调用 。然后多次 更新 或 至少 火车 对 的调用以任意顺序发生。以下是调用和正确返回值的示例:
| 参数 | 返回值 |
|---|---|
| 火车(0, 5) | 4 |
| 火车(2, 3) | 0 |
| 更新(1, 5) | 无 |
| 火车(0, 5) | 5 |
| 火车(1, 4) | 2 |
| 更新(5, 1) | 无 |
| 火车(0, 5) | 9 |
小課題
下面,在一次执行中 每个 更新 和 按字典顺序比较 火车 对 被调用的次数 P, Q 。
小課題 1 (12 点)
- 1 ≤ N ≤ 100
- 1 ≤ P+Q ≤ 200
小課題 2 (18 点)
- 1 ≤ N ≤ 5 000
- 1 ≤ P+Q ≤ 10 000
小課題 3 (30 点)
- 1 ≤ N ≤ 30 000
- P = 0
- 1 ≤ Q ≤ 20 000
小課題 4 (40 点)
- 1 ≤ N ≤ 30 000
- 1 ≤ P+Q ≤ 20 000
实施细节
制限
- CPU时间限制:4秒
- 内存限制:256 MB
注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。
接口 (API)
- 实现文件夹:training/(原型: 训练.zip)
- 竞争对手实现的文件:training.cpp
- 提交文件接口:training.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: N
- 2 行目: N 整数 给出了 A[0], A[1], ..., A[N-1] 用空格分隔。A[i] 是起始石 代表 i 的神奇力量。
- 3 行目: 整数 M。M 是P+Q 等于 。
- 从第 4 行开始 M+3 行目: 0 ≤ i < M , 如果对满足i+4 行有 3 个整数 T[i], X[i], Y[i] 用空格分隔。T[i] = 0 当什么时候 i 时间 更新(X[i],Y[i]) 拨打电话 ,T[i] = 1什么时候 i 时间 火车(X[i], Y[i]) 。
- 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
注意:示例评分程序按以下格式写入输出。- 从第 1 行开始 Q 行目: 0 ≤ i < Q , 如果对满足i+1 在线 i 第 火车 对 描述调用时应返回的返回值。