魔法の訓練 (Magical Training)

いもすは、14歳の時に魔法に目覚めた魔法少女である。

いもすは、161日後に来たるべき強敵「ウォーターリークス」を倒すために、魔力を高める訓練をしている。その訓練とは次のようなものである。

N 個の、それぞれ魔力の値が定められている石があり、1列に並んでいる。

連続したいくつかの石を選んで、それらを魔力の昇順になるように、すなわちより番号の小さい位置にはより魔力の小さい石が置かれるように並べ替えることができると、いもすの魔力を上げることができる。どの石もとても重いので、並べ替えるときは、魔法を使って隣り合う石同士を入れ替えることしかできない。

しかし、石は非常にたくさんあるため、並べ替えるのはとても大変である。魔力を上げることができる石の選び方はいくつかあるため、最も楽なものを選びたい。さらに、石の魔力の強さは時とともに変化することがある。魔力の強さの変化の仕方は、すでにいもすの魔法によりすべて予測されている。

いもすの魔法の訓練を助けるために、次に示すようなプログラムを書いてほしい。

課題

N 個の整数からなる配列 A が与えられる。石の列の左端から i+1 個目の石を石 i と番号づけ、A[i] は石 i の魔力を表すとする。

次のプロシージャを実装せよ:

N = 6, はじめの石の魔力の状態が

A = 4
1
2
2
6
5

の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後、複数回の update または train の呼び出しが任意の順番で行われる。以下に呼び出しと正しい戻り値の例を示す:

パラメータ 戻り値
train(0, 5) 4
train(2, 3) 0
update(1, 5) なし
train(0, 5) 5
train(1, 4) 2
update(5, 1) なし
train(0, 5) 9

小課題

以下、1回の実行において updatetrain が呼び出される回数をそれぞれ P, Q とする。

小課題 1 (12 点)

小課題 2 (18 点)

小課題 3 (30 点)

小課題 4 (40 点)

実装の詳細

制限

インターフェース (API)