問題一覧 > 通常問題

No.1558 Derby Live

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 62
作問者 : noya2noya2 / テスター : nok0nok0 magstamagsta
3 ProblemId : 6433 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-25 13:18:32

問題文

これから、馬 $1,2,\dots,N$ からなる $N$ 頭の馬によるレースが行われます。

レースは以下の形式に則ったものです。

  • $N$ 頭の馬が、区間 $1$ から区間 $M$ までを順番に走る。
  • 馬は 区間 $i$ に入る $\rightarrow$ 区間 $i$ を出る $\rightarrow$ 区間 $i+1$ に入る $\rightarrow$ 区間 $i+1$ を出る$\dots$ を繰り返す。
  • 区間は連続しているため、区間 $i$ を出てから区間 $i+1$ に入るまでの順位変動は無いものとして良い。
  • どの $2$ 頭の馬も、各区間へ入る瞬間と各区間から出る瞬間、同着ではない。
  • 区間 $1$ に入る馬の順番は 馬 $1,2,\dots,N$ の順番である。
  • 各区間内では $N$ 頭の馬の順位が変動する可能性がある。

ここで、$1\le l\le r\le M$ なる任意の $l,r$ について「レースのおもしろさ」$E_{l,r}$ を以下のように定義します。

  • 区間 $l$ に $i$ 番目に入った馬が区間 $r$ を $T_i$ 番目に出たとき、$E_{l,r} = \displaystyle\sum_{i=1}^{N} |i - T_i|$

  • レースが始まってから、あなたのもとに $Q$ 個のクエリが順に届きます。クエリのタイプは以下の $3$ 種類です。

    各クエリは、それ以前のクエリの情報を基に処理してください。(詳しくは制約やサンプルも確認してください)

    • type $1$ : 区間 $D$ に $i$ 番目に入った馬が区間 $D$ を $P_i$ 番目に出たという情報があなたのもとに届く。 このクエリより前の、区間 $D$ に対する情報は無視する。
    • type $2$ : 区間 $S$ を出た馬を $1$ 番目から順に全て出力する。
    • type $3$ : 区間 $L$ から区間 $R$ までの「レースのおもしろさ」$E_{L,R}$ を出力する。

    制約

  • 入力はすべて整数
  • $2\le N\le 18$
  • $2\le M\le 10^4$
  • $2\le Q\le 5\times 10^4$
  • $1\le D\le M$
  • $P=(P_1,P_2,\dots ,P_N)$ は数列 $(1,2,\dots ,N)$ の順列
  • $1\le S\le M$
  • $1\le L\le R\le M$
  • type $1$ について、 区間 $D$ に関するクエリについて、それより前のクエリで区間 $1,2,\dots ,D-1$ に関するtype $1$ のクエリが少なくとも $1$ 回ずつ存在する
  • type $2$ について、 区間 $S$ に関するクエリより前のクエリで、区間 $1,2,\dots ,S$ に関するtype $1$ のクエリが少なくとも $1$ 回ずつ存在する
  • type $3$ について、 区間 $L,R$ に関するクエリより前のクエリで、区間 $1,2,\dots ,R$ に関するtype $1$ のクエリが少なくとも $1$ 回ずつ存在する
  • 各テストケースについて、type $2$ または type $3$ のクエリが $1$ つ以上存在する。
  • 入力

    $N\ M\ Q$
    $Query_1$
    $\vdots$
    $Query_Q$
    

    $Query_i$ は、以下の $3$ つのいずれかである。

    $1\ D\ P_1 \dots P_N$
    
    $2\ S$
    
    $3\ L\ R$
    

    出力

    type $2$ の各クエリについては、$1$ 着から $N$ 着までの馬の番号を空白区切りで一行に出力し、改行してください。

    type $3$ の各クエリについては、$E_{L,R}$ を一行に出力し、改行してください。

    サンプル

    サンプル1
    入力
    3 3 7
    1 1 1 3 2
    1 2 2 1 3
    1 3 2 3 1
    2 3
    3 1 3
    1 2 1 2 3
    2 3
    出力
    2 3 1
    4
    2 1 3

    $3$ 番目のクエリまでを処理した時点では、
    区間 $1$ を出た馬の順番は $1,3,2$
    区間 $2$ を出た馬の順番は $3,1,2$
    区間 $3$ を出た馬の順番は $2,3,1$
    となっています。よって、$4$ 番目のクエリでは 2 3 1 と出力します。

    また、区間 $3$ を出た時点で馬 $1,2,3$ の着順は $3$ 着、$1$ 着、$2$ 着です。
    よって、区間 $1$ に入った馬の順番は $1,2,3$ であることに注意すると、$5$ 番目のクエリでは $E_{1,3}= |1-3|+|2-1|+|3-2|=4$ を出力します。

    $6$ 番目のクエリまでを処理した時点では、
    区間 $1$ を出た馬の順番は $1,3,2$
    区間 $2$ を出た馬の順番は $1,3,2$
    区間 $3$ を出た馬の順番は $2,1,3$
    となっています。よって、$7$ 番目のクエリでは 2 1 3 と出力します。

    サンプル2
    入力
    4 5 10
    1 1 3 4 2 1
    1 2 1 3 2 4
    2 2
    1 3 2 3 4 1
    3 1 3
    1 2 1 2 3 4
    1 4 2 1 4 3
    2 4
    1 5 3 2 4 1
    3 1 5
    出力
    4 1 3 2
    6
    4 2 1 3
    6

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。