No.833 かっこいい電車

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 50
作問者 : Shuz*Shuz* / テスター : tatyamtatyam
6 ProblemId : 3022 / 出題時の順位表

問題文

Shuz*君は $N$ 個の車両からなる電車のおもちゃを持っていて、それぞれ $1$ から $N$ までの番号が付いています。
各車両 $i$ には、かっこよさ $A_i$ が付いています。
このおもちゃは、 車両 $i$ と車両 $i + 1$ をつなげたり切り離したりできます。
Shuz*君はこのおもちゃで遊んでいて、時々つなげた車両のかっこよさを確認したくなります。
はじめすべての車両は切り離されています。
以下のクエリを処理できるプログラムを作成してください。
1. connect $x$
車両 $x$ と、車両 $x+1$ がつながっていない場合、それらを繋げる。
2. separate $x$
車両 $x$ と、車両 $x+1$ がつながっている場合、それらを切り離す。
3. remodel $x$
車両 $x$ を改造した結果、車両 $x$ のかっこよさが $1$ 上がった。
4. attractiveness $x$
車両 $x$ と、それにつながっているすべての車両のかっこよさの合計を出力する。

制約

  • $1 \le N,\ Q$ (クエリの個数) $\le 10^5$
  • $1 \le A_i \le 10^9$
  • $query$ は上述の番号 $1\dots 4$ に対応する
  • $query_i \le 2$ のとき、 $1 \le x_i < N$
  • $query_i \ge 3$ のとき、 $1 \le x_i \le N$
  • 入力はすべて整数
  • 入力

    $N\ Q$
    $A_1\ A_2\ \dots\ A_N$
    $query_1\ x_1$
    $query_2\ x_2$
    $\vdots$
    $query_Q\ x_Q$
    

    出力

    各attractiveness queryに対して、一行でかっこよさを出力してください。 最後に改行してください。

    サンプル

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

    サンプル2
    入力
    10 10
    1 3 10 20 3 4 12 41 2 40
    1 2
    1 4
    1 5
    4 1
    4 4
    3 2
    1 3
    2 5
    4 2
    4 6
    出力
    1
    27
    37
    4
    

    提出ページヘ
    下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

    言語
    問題によって提出できない言語があります。参考
    ソースコード
    ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
    テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。