すべての場所を守ろうとすれば、どの場所の兵力も少なくなる。
- 孫子『孫子』「虚実篇」
あなたは将軍に仕え、進軍計画を立てる有能な軍師です。将軍の率いる軍隊は、いくつかの地域を順番に通過しようとしています。通過した地域には守備隊を残す必要がありますが、先へ進む兵力も不足してはなりません。幸い、各地域には行軍部隊に加わる兵士が待機しています。
地域には 番から 番までの番号が付いています。軍隊が地域 を通過するときは、まず 人の兵士を守備隊としてそこに残します。その直後にも、行軍部隊には少なくとも 1 人の兵士が残っていなければなりません。その後、その地域で待機していた 人の兵士が行軍部隊に加わります。守備隊として残した兵士が再び加わることはありません。
最初の行に地域の個数 と命令の個数 が空白区切りで与えられます。
続く 行のうち 行目に、 と が空白区切りで与えられます。
2 番目の命令ごとに、必要な兵士の最小人数を 1 行ずつ出力してください。2 番目の命令がなければ、何も出力しないでください。
最初の例の最初の質問では、 人で出発すれば次のように移動できます。
各地域で加わる兵士の数や、守備隊として残す必要がある兵士の数についての情報は刻々と変わります。あなたは新しい情報が届くたびに計画表を更新し、将軍が指定した地域を通過するのに必要な兵力を伝えなければなりません。次の 2 種類の命令を処理してください。
1 i a b: 地域 で加わる兵士の数 を に変更し、守備隊として残す兵士の数 を に変更します。2 l r: 地域 から地域 まで番号の昇順で通過するために、地域 に入る時点で行軍部隊に最低何人の兵士が必要か求めます。2 番目の命令では、指定されたすべての地域で上記の規則を満たす必要があります。最後の地域でも、守備隊を残した直後に少なくとも 1 人の兵士が残っていなければなりません。各質問は、その時点の計画表に基づいて独立に判断し、実際に進軍を実行するものではありません。計画表の値が変わるのは、1 番目の命令による場合だけです。
続く 行に、命令が 1 個ずつ与えられます。
人で出発すると、地域 で守備隊を残した直後に行軍部隊に誰も残らないため、規則を満たせません。
2 番目の例の最後の質問では、 人が加わる前に 人の守備隊を残さなければなりません。したがって、最初に必要な兵士は 人です。