kagamiz.hatenablog.comこの問題、さすがに実装も定数倍も重い解法を書いてしまっていたので、別のアプローチで解き直してみました。

問題文 : King Slime解いている人数が少ない問題はなんかドキドキする(小並)

問題 : めだかの学校

問題 : Coloring Tree概要 : $n$ 頂点からなる根付き木のそれぞれのノードに色がついている. 頂点$v$ を根とする部分木にある, 異なる色の個数を数えるクエリに$m $ 個答えよ.$1 \leqq n \leqq 10^5$ $0 \leqq m \leqq 10^5$ $1 \leqq v \leqq n$ $1 \leqq$ …

問題文 : むこのどうぶつたち と しんりんのはかい

問題文 : 無矛盾な単位系

問題文Pair of Numbers概要長さ$n$ の列が与えられる. 次の性質を満たす最長の部分列をすべて求めよ. $a_l,\ a_{l+1},\ \cdots,\ a_r$ を全て割り切る$a_j\ (l \leqq j \leqq r)$ が存在する. $1 \leqq n \leqq 3 \times 10^5,\ 1 \leqq a_i \leqq 10^6$

問題 : Marked Ancestor問題概要 : 大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.$…

問題文 : Sereja and Subsequences概要 :数列${a_n}$ がある. ${a_n}$ の相異なる全ての非減少部分列${b_n}$ について, $b_1b_2\cdots b_n$ を求め, その和をmod $10^9+7$ で求めよ.$n \leqq 10^5$

問題 : Running Median数が$N$ 個与えられる. 奇数個毎に, それまでの数の中央値を出力せよ.テストケース数$T \leqq 1000$ $N \leqq 9999$ $N$ は奇数

問題文 : Running Away from the Barn問題概要 : 大きさ$N$ の木が与えられる. 距離が$L$ 以内の自分の子孫に当たるノードの個数を, すべてのノードについて求めよ. $N \leqq 200000$

Skew Heap は, meld (2 つのpriority queue をmerge する操作) ができるheapです. meld ができると, push は, 新しい要素をヒープとして親とmeld, pop は 親の子をmeldで実装できてしまいます. 計算量はならしO(log N) で便利です. (くわしくはhos さんのブ…

KOJ に載せている, (去年のAdvent Calendar に掲載していた)Big Range Query の問題文および解説です.

問題文 : 回転解法 :リストを使う. 右と下にいけるリストがあれば, 90 * n (0 ≦ n ローカルでは最大ケースに2.6sec かかり, AtCoder でも10 点分しか点数が得れないので, O(QN^2) 書いたのと同じ扱いで涙しかない...

問題文 : 建設事業解法 : つなぐ辺は隣り合うものだけ(Modern Manshion), 長方形の交差判定は上から操作(Fortune Telling), 空港のコストの方が辺より良いときはそれを使う, というJOI 問題のテクニックを総動員する問題です.点のソートをするときに, x 座標…

問題文 : Josephus Permutation解法 :アルゴリズムイントロダクションに乗っていた問題を実際にコードに起こしたもの. ヨセフスの芋の軌跡をたどったものを出力する問題. 愚直にm % n 個先までたどる線形リストなどではO(n^2) となり. TLE するだろう. そこ…

問題文 : 山の遊園地問題概要 (問題文読みづらいので) : 長さ N の数列が与えられる. 次のクエリに答えよ. 区間 [l, r] の値を v に更新する. [I l r v] [1, x] の値がはじめてv を越えるようなx を求める. [Q v] 解法 :遅延評価をするセグメント木を用いる.…

問題文 : バブルソート解法 :与えられた配列Aを, (添字, 値) を座標として座標平面にプロットする. すると, この問題は長方形の中にできるだけ多くの数を含むようにするにはどうすれば良いかを考える問題となる.愚直に数え上げを行えばこれはO(N^2) 時間で最…

問題文 : 活字印刷機解法 : Trie 木上の探索を行う. 最も長い文字を最後にたどれば, その文字の文の型を回収しなくていいため最短ですべての文字を打ち終えることが出来る. (他の文字はどのみち回収しないといけないため). コード : #include <cstdio> #include <cstdlib> #in</cstdlib></cstdio>…

問題文 : Lucky Array解法 : いつぞや誰かから「"Lucky Array"はセグメント木で解けるよ」 と聞いて, 問題を見つけたので挑戦したらそのLucky Array は別の問題だったらしい. セグメント木じゃ解けなさそうなんだよなあと思いつつ, 解法をみて勉強しようとし…

問題文 : More Queries to Array問題概要: 配列 $ \normalsize a$ が与えられるので, 区間 $ \normalsize [l,\ r] $ の値を $ \normalsize x$ に変更する. $ \normalsize \displaystyle \sum_{i = l}^{r} a_{i} \cdot (i - l + 1)^k$ (ただし $\normalsize 0…

問題文 : リンゴの出荷解法 : 濃さD のリンゴを, 区間[D, D + B + 1)に対応させて,・ある区間に値x を足す ・ある区間の和を求めることが出来れば, 出荷依頼に高速に答えることができる. これは, Starry Sky 木を改造することで実現することが可能である.た…

問題文 : 魚解法 : 初めに, 尺取り法で, 起こりうる魚の組み合わせ(赤a 匹, 緑b 匹, 青c 匹 以下の組み合わせなら全て作成可能である) というものを列挙する. これをa * b * c の直方体として扱う. その後に, セグメント木で体積を, 以下の要領で求めていく.…

問題文 : 報告解法 :まず, 問題文の例を解析する. 報告先でサイクルになっている頂点達について, サイクル内の頂点v に仕事の報告が来れば, 必ず他の頂点でも仕事の報告が来ることがわかるので, 閉路を潰す.次に, 閉路を潰して出来たグラフの逆辺からなるグ…

問題文 : 忍者の派遣解法 : 各頂点でpriority queueを持ち, dfs を行い, 給料のコストが大きい頂点から予算を超える分だけqueueから取り除く.これだけではO(N * NlogN) = O(N^2 log N) の計算量となってしまうが, 頂点を併合する際に, 短い方のqueueを併合す…

問題文 : Query on a tree II解法 :複数テストケースなので初期化する位置に気をつけないと死んでしまう問題 (ぼく死んでしまいました).距離を求めるところはeuler-tourっぽくやるのも, doubling でやるのもよしです. k 番目の頂点は, 根からの深さとlca(u, …

問題文 : Sliding Window解法 :見た感じセグメント木でもよさそうだが, 蟻本でdequeを使うO(N) 解法が紹介されていたので, dequeの練習がてら書いてみた. dequeステキ, 便利. やはり書くと分かりやすい.dqでは, i dq2では, i a[j] となるようにdequeにデータ…

問題文 : Dungeon (I)解法 : クエリでの求める距離fs_iと, スタートからの最短路についてソートし, BITで数え上げを行うと O(N log N)時間でこの問題を解くことが出来る. クエリや最短路は, 数に対し範囲が大きいので座標圧縮を行うと管理が楽になると考えら…

問題文 : Mars Map解法 : 座標において長方形が重なっている領域の面積を求める問題. 平面走査を行った.具体的には, ある長方形について, (x1, y1, y2)の間その領域を存在することにして, (x2, y1, y2)をその領域を消すタイミングとする.これをO(logN)で実現…

問題文 : 星空解法 : N個ある各星のLについて, そのLで囲める星の最大値を求める.ここで, 走査をする際に, x軸のみを走査し, y軸はセグメント木で, "ある点に於いて観測できる星の最大値"を管理すると, x軸の走査がO(N), その過程でのセグメント木の走査がO(…