Garsia–Wachs 算法(石子合并)

• 在序列中找到连续的三个值$x,y,z$，使得$x \leq z$。因为序列结尾的标志值大于之前的任意两个有限值，所以总是存在这样的三元组。
• 从序列中移除$x,y$，并创建一个新的树节点作为$x$和$y$父的节点，值为$x+y$。
• 在原来$x$的位置以前大于等于$x+y$且距$x$最近的值的右边重新插入新节点。因为左标志值的存在，所以总是存在这样的位置。

int merge(){
    int k = vec.size() - 2 ;
    for(int i = 0 ; i + 2 <  vec.size() ; ++ i){
        if(vec[i] <= vec[i+2]){
            k = i ;
            break ;
        }
    }
    int te = vec[k] + vec[k+1] ; 
    vec.erase(vec.begin() + k) ;
    vec.erase(vec.begin() + k) ;
    int t = -1 ;
    for(int i = k - 1 ; i >= 0 ; -- i ){
        if(vec[i] >= te){
            t = i ;
            break ;
        }
    }
    vec.insert(vec.begin() + 1 + t,te) ;
    return te ;
}
void solve(){
    cin >> n ;
    int t ;
    for(int i = 1; i <= n ; ++ i){
        cin >> t ;
        vec.push_back(t) ;
    }

    for(int i = 1; i < n ; ++ i){
        ans += merge() ;
    }
    cout << ans << endl ;
}