yukicoderTweet遅延伝搬セグメント木の復習をしたので、beetさん作問のセグ木コンテスト(2019/9/6開催)の問題を解いてみた。難しいけど面白かった(解けたので)。値を求めるクエリは区間[l,r]で何回数が変わったかを調べる関数。いくつあるかも欲しいけどどうする?クエリ先読み。指定区間の各値が「高い」か、即ち、その区間の自分より左に自分より大きな値を持たないかを見て、「高い」値の個数を返すある値がどの範囲で「高い」と言ってもらえるかを調べておく区間の始点はRMQなりセグ木maxクエリで二分探索すれば分かる。なる)問題はgcdの方で何かとxのgcdは必ずxの約数になる(ということは1〜xの範囲に収まる)はずとりあえず遅延操作の表現を考える。みたいな交換が効くので縮約できるとすると操作列が長さ2を超えることはなさそう。gcd,の4種類しかありえない)遅延操作の方はこれで良いとして、各ノードが(maxとsum以外に)持っておくべき値は何?素因数分解して集計しても計算は簡単にできないな何が何個あるかだけmapにして持たせる?(それだとmax,sumの更新にも都合がよさそう)でも(gcd後なら)xの約数の個数を超えないとはいえそれなりに大きいよね...時間制限が5secなので少しは重くても行ける?最初に投げたやつは大きな(大きそうな)データでTLE。(TLEが1つ出るとその後のジャッジをしないの賢いなあ)しかし巨大データを貰ってきて試したら48secほどかかっていた。f(&a,b)みたいに書き換えたりとか巨大mapを含む部分のコピーをできるだけ減らしたい...なるべく参照渡しにする10〜12secで終わるようになった。(でも5secにはまだ遠い)それを投げてみたら→ACお時は2020年。まとめコンテスト〈EDPC〉補習篇(T,U,...コンテスト後に読んだ問題たち。»@naoya_t自然言語処理とか機械学習とか競技プログラミングとか。競プロ精進記録は別ブログ🔒に移しました。yukicoder遅延伝搬セグメント木の復習をしたので、beetさん作問のセグ木コンテスト(2019/9/6開催)の問題を解いてみた。サウスタワー23Fなんで自分に参加権が来たのかよく分からないオンサイトイベントに参加してきた話。146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。"なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。14:00-FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。過去問コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。