区間に関するクエリ
差分だけ更新していく系の問題！！！ 問題へのリンク editorial 類題集 (めちゃむずいのもある) drken1215.hatenablog.com 問題概要 正の整数 が与えられる。長さ の数列 のスコアが次のように定まる。 各 に対して以下の値を合算する のとき： のとき： を…
いもす法 問題へのリンク editorial 問題概要 要素からなる数列がある。初期状態では全要素の値が 0 である。以下の 回の操作を行なって得られる数列を出力せよ。 各クエリでは整数 が与えられる。区間 に対して、初項 1、交差 1 の等差数列を加算する 制約 …
これは天才！！！ 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …
面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…
実家なんだと思うけど...意外とはまりやすい問題な気 がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…
これと似てる！！！ これの解法 3 みたいなやり方をイベントソートって呼ぶのね。 drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う 整数 が与えられて、区間 […
こういうのを得意になるぞー！！！ でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…
Mo のアルゴリズムの練習第三弾！！！！！ 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内について、各数値 について が何個出現しているかを として表して、 を求め、その総和を求めよ 制約 考えたこと…
Mo のアルゴリズムの練習第二弾。 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に最も多く登場する値が、何回登場しているかを答えよ 制約 考えたこと Mo の練習第二弾。 最頻値の頻度を求めるのは、…
種類数クエリをマスターするぞ！ 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に何種類の整数があるかを答えよ 制約 解法 1： BIT (区間加算、1 点取得) まずは BIT を用いる方法から。 考えやすいよ…
えーーーこれが平方分割的解法って天才すぎでは 問題へのリンク 問題概要 人が一直線上を、初期位置 、速度 で等速直線運動を行う。以下の 個のクエリに答えよ: 秒後に座標 から座標 までの間にいる人数を数えよ 制約 考えたこと が 以下と小さいことが大き…
