# CSES Increasing Array Queries
> https://cses.fi/problemset/task/2416/
>
CSES RMQ Problem set 裡遇到的難題，直接把我輾過去，筆記一下。
給長度$N$之數列，有$q$次詢問，定義一次操作為將任意一數加一，問使區間$[x, y]$變成遞增數列的最少操作，$N, q \le 2 \times 10^5$， $1 \le x, y \le N$。

對於任意區間$[x, y]$，假如$a_{l}$為其中最大的數($x \le l \le y$)，馬上想到的是區間內$l$右邊的數都要加到$a_l$，於是前綴和可以派上用場。

再來是說$l$左邊那些可能亂七八糟的數該如何處理?如果從$x$往右邊走，遇到的第一個$\ge a_x$的數$a_j$，那麼在區間[x, j-1]都要讓他加到$a_x$，於是如何快速地跳到$a_l$變成關鍵的點。

如果建一個倍增表紀錄往右跳到$\ge$自己的點，是否能夠順利地跳到$a_l$? 定義$nxt(i, k)$為$i$右邊第$2^k$個$\ge a_i$的點，

假如從$x$開始跳，假如說$nxt(x, 4)$超過$y$了，那我們先跳到$nxt(x, 3) = x'$，可以馬上發現的是$nxt(x', 3)$一定會超過$y$，所以從$x$開始，$k$從最大值開始遞減，每次跳到右邊第$2^k$個$\ge$自己的點是可以跳到區間最大值點$l$的，於是維護一下$cnt(i,k)$表示跳到右邊第$2^k$個點要多少次操作就好。

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const ll Inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int n, q;
ll a[N], cnt[N][20], pre[N];
int nxt[N][20];

void solve(){
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    a[n+1] = Inf;
    pre[0] = 0;
    for(int i=1; i<=n; i++) pre[i] = a[i] + pre[i-1];

    stack<int> st;
    st.push(n+1);
    for(int k=0; k<20; k++) nxt[n+1][k] = n+1, cnt[n+1][k] = 0;
    for(int i=n; i>=1; i--){
        while(!st.empty() && a[i] > a[st.top()]) st.pop();
        nxt[i][0] = st.empty() ? n+1 : st.top();
        cnt[i][0] = a[i] * (nxt[i][0] - i - 1) - (pre[nxt[i][0] - 1] - pre[i]);
        st.push(i);
    }
    
    for(int k=1; k<20; k++){
        for(int i=1; i<=n; i++){
            nxt[i][k] = nxt[nxt[i][k-1]][k-1];
            cnt[i][k] = cnt[i][k-1] + cnt[nxt[i][k-1]][k-1];
        }
    }

    for(int i=1; i<=q; i++){
        int x, y; cin >> x >> y;
        ll ans = 0;
        for(int k=19; k>=0; k--){
            if(nxt[x][k] <= y){
                // cout << "x=" << x << " k=" << k << " jump to" << nxt[x][k] << " with" << cnt[x][k] << endl;
                ans += cnt[x][k];
                x = nxt[x][k];
            }
        }
        if(x < y){
            ans += a[x]*(y - x) - (pre[y] - pre[x]);
        }
        cout << ans << endl;
    }

} 
 
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--)
    solve();
 
    return 0;
}

### 時間複雜度 ：$O(NlogN)$

###### tags: `stack` `binary jumping`