Boring Problem

倍增思想的模板题，注意写法就行了。

#include<bits/stdc++.h>
#define ll long long
#define P pair<int, int>
#define PP pair<int,pair<int, int>>
#define pb push_back
#define pp pop_back
#define lson root << 1
#define INF (int)2e9 + 7
#define maxn (int)1e5 + 7
#define rson root << 1 | 1
#define LINF (unsigned long long int)1e18
#define mem(arry, in) memset(arry, in, sizeof(arry))
using namespace std;

int T, n, K, q;
int a[maxn], pos[maxn][20], use[maxn];
ll sum[maxn];

int get(ll x) {
    int l = 1, r = n + 1;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(sum[mid] <= x) l = mid + 1;
        else r = mid;
    }
    return l;
}

void Inite() {
    mem(use, 0);
    mem(pos, -1);
    for(int i = 1; i <= n; i++) {
　　　　 // 不合法的位置就不要跳
        if(a[i] > K) use[i] = 1;
        else pos[i][0] = get(sum[i - 1] + K);         
        use[i] += use[i - 1];
    }
    for(int i = 1; (1 << i) <= n; i++) {
        for(int j = 1; j <= n; j++) if(pos[j][i - 1] != -1) {
            pos[j][i] = pos[pos[j][i - 1]][i - 1];
        }
    }
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        mem(a, 0);
        scanf("%d %d %d", &n, &K, &q);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + (ll)a[i];
        Inite();
        while(q--) {
            int l, r;
            scanf("%d %d", &l, &r);
            if(use[r] - use[l - 1] > 0) { puts("-1"); continue; }

            int res = 0;
            for(int i = 19; i >= 0; i--) {
                if(pos[l][i] <= r && pos[l][i] != -1) {
                    l = pos[l][i];
                    res += (1 << i);
                }
            }
            printf("%d
", res + 1);
        }
    }

    return 0;
}