""" query_0 が Σ A[i] (l≤i≤r-1) を出力 query_1 が l≤i≤r-1 について A[i] を A[i]*b + c に更新する X[l,r): Σ A[l,r) lazy[i] (更新を保存しておく配列) の２つの配列をもち、 ・op_data: X＊X →X (X[l≤i

始点ソートして、L ≦ i ≦ R でd[ i ] = min( d[ i ], d[ L ] + c ) で更新していけば終わり。 答えは d[ n-1 ] で、d[ n-1 ] = INF なら -1 を出力する d[ i ] の一点取得、L ≦ i ≦ R の区間更新なのでセグ木を使えば簡単。 import sys read = sys.stdin.buf…

python だと難易度が爆上がりするやつ。 E - Exclusive OR QueriesCPSCOのsession1のEをPythonで通そうと頑張ってみたけどダメそうということがわかった(はい)(ごめんなさい)— てんぷら (@tempura_cpp) May 12, 2019 本編まで飛ばしていいよ。 やるべき動作…

NOMURA プログラミングコンテスト 2020 A,B,C の3完 ABC170 A,B,C,D の4完でした。 土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1…

まんまこれ。 区間に含まれる区間の数をカウントするクエリにたくさん答えたい - 問題解決の宝石箱 終点でソートすることにより、それまでに出てきた区間の終点が、今見ている区間の終点よりも小さいことが保証され、始点の位置だけセグ木で保管すれば、クエ…

k = 0 から順番に (A[k*2],B[k*2]), (A[k*2+1],B[k*2+1]) を (A[k*2]+B[k*2])*A[k*2+1]+B[k*2+1] と計算していく問題。 セグ木を使うと、(A[k*2]*A[k*2+1], B[k*2]*A[k*2+1]+B[k*2+1]) の結果を (A[k], B[k])に保存できるので、求める答えは sum(A[1]+B[1]) …

セグ木の練習。木というているけど、使いどころはグラフ問題ではなく、ソートされた数列で、特定の区間の最小値や公約数を求めたり、特定の区間の値を変更するときに使う。 愚直にやると N^2かかるが、heap を使おうとすると頭が痛くなるときに便利。 今回の…