SRM404 500 : KSubstring
さぼりすぎた
この調子で後、96回出来る気がしないぞ。
問題概要
- 数列Aが面倒くさい形で与えれます。
- s(i,k) = A[ i ] + A[ i + 1 ] + ... A[ i + k - 1 ] と定義されます。
- abs( s(i,k) - s(j,k) ) ( j >= i+k ) の最小値とその時のkを返して下さい。
- 複数の最小値があった場合kの最大を返して下さい。
解法
- 数列の累積和Sを求めます。
- はじめに k の値を決め打ちします。
- マージソートの過程を保存するセグメントツリーを書く要素の値をS[i+k] - S[i] として作ります。
- 各 i について、s(i,k) をx として [ i+k, n ) の区間にある x との最近値との差を上記のセグメントツリーを使って求めます。
- 後は答えを集計して出すだけ（long long トラップに注意 )
ソースコード
感想
区間の最近値を出すセグメントツリーライブラリ化したほうがいい気がする。
メモリがやばい時は平方分割の方とも使い分けないといけないから両方ペタ出来るようにしたほうが良いのかもしれない。
（seg木のほうがはるかに速いから基本ソッチのほうがいいけど、
空間計算量がN log Nで64MB越える時が割りと多いから怖い）
10 ^ 5 の int を取ると 6MB くらい
5 * 10 ^ 5 の int でも 38MB くらいだったので案外使えるかもしれない。
でも、pair とか取るとやっぱり結構やばいかも
