ST表加倍增0分求条（必关）

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
using ll = long long;
ll n, q, v, nxt[N], f[N][50], l, r, mid, x, p, k, g[N][50], num[N][50];

struct node{
    ll d, w, id;
}a[N];

ll log_2(ll x){
    ll sum = 1, cnt = 0;
    while(1){
        if(sum > x){
            return cnt - 1;
        }
        sum *= 2;
        cnt++;
    }
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i].d >> a[i].w;
        f[i][0] = a[i].d;
        a[i].id = i;
    }
    a[n + 1].d = 1e18, a[n + 1].w = 1e18;
    a[n + 1].id = n + 1, f[n + 1][0] = a[n + 1].d;
    for(int len = 1; (1 << len) <= n + 1; len++){
        for(int i = 1; i + (1 << len) - 1 <= n + 1; i++){
            f[i][len] = max(f[i][len - 1], f[i + (1 << (len - 1))][len - 1]);
        }
    }
    for(int i = 1; i <= n; i++){
        nxt[i] = n + 1;
    }
    nxt[n + 1] = n + 1;
    for(int i = 1; i <= n; i++){
        l = i + 1, r = n + 1;
        while(l <= r){
            mid = (l + r) / 2;
            p = log_2(mid - i + 1);
            x = mid - (1 << p) + 1;
            if(max(f[i][p], f[x][p]) > a[i].d){
                r = mid - 1;
                nxt[i] = min(nxt[i] , mid);
            }else{
                l = mid + 1;
            }
        }
    }
    for(int i = 1; i <= n + 1; i++){
        g[i][0] = nxt[i];
        num[i][0] = a[i].w;
    }
    for(int len = 1; (1 << len) <= n + 1; len++){
        for(int i = 1; i + (1 << len) - 1 <= n + 1; i++){
            g[i][len] = g[g[i][len - 1]][len - 1];
            num[i][len] = num[i][len - 1] + num[g[i][len - 1]][len - 1];
        }
    }
    while(q--){
        cin >> k >> v;
        while(1){
            if(k == n + 1){
                cout << 0;
                break;
            }else if(v <= a[k].w){
                cout << k;
                break;
            }else{
                p = log_2(n + 1 - k + 1);
                for(int j = p; j >= 0; j--){
                    if(v >= num[k][j]){
                        v -= num[k][j];
                        k = g[k][j];
                    }
                }
            }
        }
        cout << '\n';
    }
    return 0;
}