本题一开始想的是用f[i][j]表示从i开始长度为2^j的和，然后每次查询的时候利用倍增去快速找到某一段的最右边。结果超时了，后来想了下，万一卡一个n段的数据，就挂了。而且这样倍增还不如直接O（1）预处理每个点到下一段的距离来得快。

题意:

给你一个长为n的序列a和一个常数k

有m次询问，每次查询一个区间[l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k

如果这一次查询无解，输出"Chtholly"

思路：
用f[i][j]表示从i出发走了2^j段的最远的点的下一个点。
显然有：f[i][j]=f[f[i][j-1]][j-1]
对于f[i][0]来说，可以O(n)预处理或者二分查找前缀和数组。
然后对每次询问去倍增查找就好了。
对于无解的情况其实就是看[l,r]中是否存在一个数字超过K的。那么预处理一下maxi[i]数组记录前i个数里面超过k的个数，做差判断就可以。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,a[1000040],maxi[1000040];
ll f[1000040][22],sum[1000050];
void init(){
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++){
        maxi[i]=maxi[i-1]+(a[i]>k);
    }
}
int erfen(int l){
    int x=lower_bound(sum+1,sum+1+n,sum[l-1]+k+1)-sum;
    return x;
}
void ST(){
    for(int i=1;i<=n;i++)f[i][0]=erfen(i);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    init();
    ST();
    while(m--){
        int l,r,ans=1;
        scanf("%d%d",&l,&r);
        if(maxi[r]-maxi[l-1]>0)cout<<"Chtholly"<<endl;
        else {
            for(int j=20;j>=0;j--){
                if(f[l][j]&&f[l][j]<=r){
                    l=f[l][j];
                    ans+=(1<<j);
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

一点疑问：
我一开始想用f[i][j]表示从i走过2^j段的最远距离的点（不是下一个）。这样写感觉也是可以的，但是总是只能过30%，对倍增还是不熟啊。希望有大神能指点一二。