← 返回题目列表

AtCoder · ijpc_training

C. 魔法训练

中文机器翻译题面 查看原题

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) 或 至少 火车(p, q) 在调用 之前仅调用一次。该过程没有返回值。
  • 具有以下参数的过程 更新(i,x):
    • i -- 魔力发生变化的石头数量。
    • x -- 魔力变化后的石头 i 的魔力。1 ≤ x ≤ N 。
    此过程被调用多次。一次召唤,对应一次魔力变化。该过程没有返回值。
  • 具有以下参数的过程 火车(p, q) 在调用:
    • p -- 要排序的最左边的石头数量。0 ≤ p < N 。
    • q -- 要排序的石头的最右边的编号。p ≤ q < N 。
    此过程被调用多次。一通电话就是一块石头 p 卡拉石 q (包括两端)通过替换相邻的棋子。 从位置 p 相当于朝着 q 位置进行魔力升序排序的训练。每次调用都需要进行相应的训练石头更换的最低数量必须作为返回值返回。不过,石子实际上并没有重新排列,只是确定了更换的次数。

例

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 第 火车 对 描述调用时应返回的返回值。