C - 魔法の訓練 (Magical Training) Editorial /

Time Limit: 0 msec / Memory Limit: 256 MB

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

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

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

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

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

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

課題

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

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

  • 次のパラメータを持つプロシージャ init(N, A):
    • N -- 石の数。石には左から順に 0 から N-1 までの異なる整数の番号がつけられている。
    • A -- 石の魔力を表す整数の配列。0 ≦ i < N に対し 1 ≦ A[i] ≦ N を仮定してよい。
    このプロシージャは最初に update(i, x) または train(p, q) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
  • 次のパラメータを持つプロシージャ update(i, x):
    • i -- 魔力が変化する石の番号。
    • x -- 魔力が変化した後の石 i の魔力。1 ≦ x ≦ N を仮定してよい。
    このプロシージャは複数回呼び出される。1回の呼び出しは1回の魔力の変化に対応する。このプロシージャは戻り値を持たない。
  • 次のパラメータを持つプロシージャ train(p, q):
    • p -- 並べ替える石の左端の番号。0 ≦ p < N を仮定してよい。
    • q -- 並べ替える石の右端の番号。p ≦ q < N を仮定してよい。
    このプロシージャは複数回呼び出される。1回の呼び出しは石 p から石 q (両端も含む)までの石を、隣り合う石を入れ替えることによって p の位置から q の位置に向かって魔力の昇順に並べ替える訓練に対応している。それぞれの呼び出しは対応する訓練のために必要な最小の石の入れ替え回数を戻り値として返す必要がある。ただし、実際には石の並べ替えは行わず、入れ替えの回数だけを求めるものとする。

例

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回の実行において update と train が呼び出される回数をそれぞれ 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/ (プロトタイプ: 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 回目に update(X[i], Y[i]) という呼び出しが行われ、T[i] = 1のとき i 回目に train(X[i], Y[i]) が呼び出されることを表す。
  • 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
    注意:採点プログラムのサンプルは次の書式の出力を書き出す。
    • 1 行目から Q 行目: 0 ≦ i < Q に対し、i+1 行目には i 回目の train 呼び出しの際に返されるべき戻り値が書かれている。