区间的连续段 - 倍增DP

题目链接：https://ac.nowcoder.com/acm/contest/82/B

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL a[1000005], s[1000005]={0}, f[1000005][25];
int main(){

    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        s[i]=s[i-1]+a[i];
    }
    for(int i=1; i<=n; i++){
        int pos=upper_bound(s+i, s+n+1, (s[i-1]+k))-s;
        f[i][0]=pos;
    }
    for(int i=0; i<=22; i++){
        f[n+1][i]=n+1;
    }
    for(int i=1; i<=22; i++){
        for(int k=1; k<=n; k++){
            f[k][i]=f[f[k][i-1]][i-1];
        }
    }
    while(m--){
        int x, y, ans=0; scanf("%d%d", &x, &y);
        for(int i=22; i>=0; i--){
            if(f[x][i]&&f[x][i]<=y){
                ans+=(1<<i);
                x=f[x][i];
            }
        }
        //如果a[x]>k那么f[x][i]=i这个位置跳在原位置
        if(f[x][0]>y){
            cout<<ans+1<<endl;
        }
        else{
            cout<<"Chtholly"<<endl;
        }
    }

    return 0;
}