Pishty and Triangles [CodeChef March Challenge 2018 Div1 D]

https://www.codechef.com/MARCH18A/problems/PSHTRG

N要素の配列Aがある。
これについてQ個の以下のクエリを処理する。
「1 pos val」 : A[pos]をvalにする
「2 l r」 : A[l], A[l+1], .., A[r]から3つ作って三角形を作るときに、三辺の長さの和の最大値は？（作れないなら0を出力）

前提知識

• セグメントツリー（区間max）

解法

https://www.codechef.com/viewsolution/17611626

長さa≧b≧cを使って三角形が作れる為にはa＜b+cである必要がある。
この条件を正しく考えて範囲で考えるのはとても難しいように思える。
もうちょっと条件を言い換えたい。
　
A[l],A[l+1],..,A[r]を降順ソートしたものをv[0],v[1],..とする。
一番長い辺をA[i]とすると、A[i+1],A[i+2]を使うのが最適。
最適でかつ、条件を満たしやすい。
また、条件をA[i],A[i+1],A[i+2]で条件を満たさない場合、A[i+1]とA[i+2]のどちらかがA[i]/2未満の数となる。
よって、最大の辺を順番に考えていった時にv[64]くらいまで行くと0になってしまうので、必ず何処かで条件を満たす。
よって、A[l],A[l+1],..,A[r]から最大64個位取ってきて、降順で条件を満たすものを探していけばいい。
　
区間から最大を64回取ってくるときは、区間maxのセグメントツリーを使って64回取得と更新を繰り返しながら取ってくればいい。
あとは、最大値を答える。
本番は50回取ってくると通った。

int N, A[101010], Q;
SegTree<pair<int, int>, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) st.update(i, make_pair(A[i], i));
 
    rep(q, 0, Q) {
        int T; cin >> T;
        if (T == 1) {
            int pos, val; cin >> pos >> val;
            pos--;
 
            A[pos] = val;
            st.update(pos, make_pair(A[pos], pos));
        } else {
            int l, r; cin >> l >> r;
            l--;
 
            vector<int> v;
            vector<pair<int, int>> memo;
 
            rep(i, 0, 50) {
                auto p = st.get(l, r);
                if (p.first < 0) break;
 
                v.push_back(p.first);
                st.update(p.second, make_pair(-1, -1));
                memo.push_back(p);
            }
 
            int n = v.size();
            ll ans = 0;
            rep(i, 0, n - 2) {
                ll a = v[i];
                ll b = v[i + 1];
                ll c = v[i + 2];
 
                if (a < b + c) chmax(ans, a + b + c);
            }
 
            printf("%lld\n", ans);
 
            fore(p, memo) st.update(p.second, p);
        }
    }
}