segtree

ABC334F スタートとゴールの vertex を \(0\), それ以外の vertex を \(1, \cdots , N-1\) として， \(N\) 個の頂点で書き直したバージョンで説明する． \(d_{i,i+1}\) を \(i\) から \(i+1\) への距離とおく． 解法 0: Segtree まず簡単なバージョンの問題を考える． Eary: プレゼントの制限無し プレゼントを無限に持てるという場合は， 0 に戻る必要がない． よって，\(i \rightarrow i+1\) の距離 \(d_{i,i+1}\) の和が答え． Normal: プレゼントの制限有り 何回か …

ABC276F 部分問題 \(a\) を size \(N\) の vector， \(i \in N\) とする． \(a_{[0,i)}\) において， \(a_{i}\) 未満の個数と \(a_{i}\) 以上の和が分かれば十分． これらは segtree で実装可能． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" ll op(ll a, ll b) {return a+b; } ll e() {return 0LL;} int main() { ll n,m; cin >> n; vll a…

ABC254F 長方形領域における GCD を求める問題． 2次元の計算を 1次元に落とす． 気持ちとしては，和や差によって GCD が変わらないことを利用して， 左上を基準のマスとして，残りは差分で計算したい． 行と列の差分を別々に計算することで，計算量を減らす． \(d = GCD\) とおく． \begin{align} d(a+b_{0}, a+b_{1}, a+b_{2}) &=& d(a+b_{0}, b_{1}-b_{0}, b_{2}-b_{1}) \\ \end{align} であることから， \begin{align} d_{i \in H,\,j \in W}(a_{i}…

ABC253F とりあえず欲しいのは出力クエリでの \((i,j)\) 成分の値． これは， \(i\) 行目に対する最後の代入クエリと，それ以降の \(i\) 行目に対する加算クエリの和が分かれば十分． これらは，クエリを先読みすることで得られる． 必要なデータ構造は，範囲加算と点取得． 点加算，点取得でもimos法の要領で代用可能． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, m, q; cin >> n >> m >> q; vll type(q), a…

ABC231F まず，求める答えを式に直してみる． \(i,j \in N\) であって \(a_{i} \geq a_{j}\) かつ \(b_{j} \geq b_{i}\) となる 組\(\,(i,j)\) の個数を数える． \(b\) はマイナスを掛けて順序を反転させると， \(a\) と同じ形になって楽． 平面走査で数える． \(a\) を小さい順に調べれば， \(a_{i} \leq a_{j}\) の条件は自動的に満たす． 言い換えると， \(a_{i}\) について調べている時点で， \(a_{i} > a_{j}\) となる \(j\) は過不足なく調べ終わっている． \(=…

ABC221E \(l < r\) とする． \(a_{l} \leq a_{r}\) を満たしていれば，その間の項は自由に選べるので， 答えは \begin{align} \displaystyle \sum_{ l, r \in N \times N \\ l < r \\ a_{l} \leq a_{r} } 2^{r-1-l}. \end{align} これを \(r,l\) の項に分解すれば， 各 \(r\) に対して $$ \displaystyle \sum_{l < r \\ a_{l} \leq a_{r}} 2^{-l} \ \ \cdots (*) $$ が求まれば十分．…

PAST007L 参考にした実装 https://blog.hamayanhamayan.com/entry/2021/07/24/203450 全ての \(j\) を求めるとあるが，まずは \(1\) 個求める． 特に，最小の \(j_{0}\) を求められれば， \(j_{0}+1\) 以降の中から 最小の \(j_{1}\) を求めることができる． これを繰り返して全ての \(j\) を求められるペア \((a_{i}, i)\) に対してsegtreeを考えれば， 最小の \(a_{i}\) が複数あった場合に， \(i\)が最小のものが手に入る． 使っている記号，マクロ等 "http…