Codeforces Round #569 (Div. 2)

ばちゃ

5問中3完でした。うーん厳しい。このくらいの難易度なら全完目指していいくらいなので、悲しいですね。Dはおもしくなかったですが、Eは割と学びを得たと思います

図を見てどうにかします。やるだけ。

問題：N個の整数列Aの各要素についてAi*(-1)-1を行える。積を最大化する列を求めよ

考察：

絶対値を大きくするのは負のほうです。

Nが奇数のとき、全て負にするとマイナスになってしまうので1つだけ正にします

これは絶対値の大きいものを正にすればよいです。(倍率が(Ai-1)/Aiなので)

また、操作は各1回とありますが、冷静に式変形すると何回しても同じだとわかり簡単です

問題：N個の要素を持ったスタックが与えられる。前の２要素を取り出し、大きい方を前に、小さい方を後ろに入れる。Q個のクエリでこの操作をqi回目に行ったとき取り出す要素2つを出力せよ

考察：

全体の最大値Mが先頭にきたとき、残りの配列をループすることになります

したがってMが先頭に来るまで愚直にシミュレートして、もしそれより多い回数が指定されたら残りのスタックの%(N-1)番目を出力すればよいです。

問題：N*Mのグリッドを1，1から移動する。移動ベクトルに重複がないようにするとき、全てのマスを1回ずつ移動する方法を構築せよ

考察：

わからん。難しめの構築だから、必ずできそう。通してる人が多いので多分パターンが決まってる系ですね

解説：

中心から対称に移動すればよい

問題：N個の料理がai円で売られている。M人の生徒が順番に料理を購入する。それぞれbi円所持している。各生徒は残っている料理で、最も高いものを購入する。

あなたはM+1人目の生徒で、無限にお金を持っている。どの料理が購入できるか。

Q個のクエリでai,biを変更していく。Q回目のクエリの後の結果を求めよ

考察：

ｘ以上の料理の数をax、生徒の数をbxとします

もしax>bxならその料理を購入できます

ここで単調性はありません

セグ木でax-bxの最大値を持ちます。最大値が1以上なら、そのようなｘの中で最大なものが求まればよいです。

クエリではai以下を-1、x以下を+1などする必要があります。

これは遅延伝播セグ木で実現可能である。

実装：

nodeとは別にdelayを持ちます。

各nodeを見るときに

delay[k] => node[2*k+1],node[2*k+2],delay[2*k+1],delay[2*k+2]と足します

delay[k]=0に初期化します

この操作で区間全てに値を足す操作がO(logN)で実行できます

次に1以上のindexの取得です。

遅延伝播をさせたあと、子nodeを見て1以上の点に移動するだけなので簡単です。O(logN)で行えます

以上でO(N+QlogN)で解くことができました。