【区间的连续段】--ST表，倍增

题意：给出n个数和k，m次查询，每次输出区间可以最小分割成多少和<=k的段

这题是ST表的应用，我们利用倍增的思想，对于每个位置，我们用dp[i][j]表示从i开始之后每一段割2^j个数字，最右端点可以到哪，查询的时候从大端点查到小端点，一定可以把整个区间拼接完成，要是有非法的数字，右端点则是他自己，判断一下即可

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
inline int read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; } ;
const int maxn=1e6+5;
ll dp[maxn][25],pre[maxn];//pre记录前缀和,dp[i][j]表示从i开始之后分割成2^j段，最右端可以到达哪里
int main()
{
    int n=read(),m=read(),k=read();
    rep(i,1,n) pre[i]=read(),pre[i]+=pre[i-1];
    rep(i,0,21) dp[n+1][i]=n+1;//第n+1位的最右端永远都是n+1，dp初始化
    for(int i=n;i>=1;i--)
    {
        dp[i][0]=upper_bound(pre+1,pre+1+n,pre[i-1]+k)-pre;//用upper_bound之后可以统一右端点为dp[i][j]-1
        //printf("%d\n",dp[i][0]);
        rep(j,1,21) dp[i][j]=dp[dp[i][j-1]][j-1];
    }
    //printf("%d\n",dp[2][0]);
    //printf("%d\n",dp[4][0]);
    //printf("%d\n",dp[2][1]);
    //for(int i=21;i>=0;i--) printf("%d\n",dp[2][i]);
    rep(i,1,m)
    {
        int l=read(),r=read();
        ll ans=0;
        for(int j=21;j>=0;j--)
        {
            if(dp[l][j]<=r) ans+=(1<<j),l=dp[l][j];
        }
        if(dp[l][0]<=r) puts("Chtholly");
        else printf("%d\n",ans+1);//因为右端点多了一个数字，那那个数字自成一段
    }
}