原题链接

题意：

给你一个长为n的序列a和一个常数k。有m次询问，每次查询一个区间[ l , r ]内所有数最少分成多少个连续段，使得每段的和都< = k。如果这一次查询无解，输出" C h t h o l l y "。

思路：

先考虑简化版：给定一个序列和k，问将该序列最少分成多少个连续段，使得每段的和都< = k。

从前向后枚举，对于每次结果都贪心的考虑，如果当前和大于k就重新开一段。

也就是说需要处理的就是，对于每个点能够到达的最远的点。

回到这个题，类比的处理一下。但是加了区间限制之后，最远的点不一定在区间里，所以略微变形一下：维护d p [ i ] [ j ]表示从点i开始，分成2 j段，最远能够到达的位置的下一个点。

由于2 j = 2 j − 1 + 2 j − 1，所以d p [ i ] [ j ] = d p [ d p [ i ] [ j − 1 ] ] [ j − 1 ]

对于d p [ i ] [ 0 ] = x，找一个位置[ i , x − 1 ]使得该段的和恰好小于k kk;s u m [ i ] sum[i]sum[i]表示a aa的前缀和。也就是说s u m [ x − 1 ] − s u m [ i − 1 ] < k ， s u m [ x − 1 ] < s u m [ i − 1 ] + k sum[x-1]-sum[i-1]

对于查询：" C h t h o l l y "的情况就是a [ i ] > k , l < = i < = r。用t o t [ i ]表示前i个数中> k的数的个数，每次查询t o t [ r ] − t o t [ l − 1 ]，如果大于0，就是" C h t h o l l y "

对于其他情况，从大到小枚举，类似二进制拆分的原理。[ l , s t [ l ] [ i ] )表示将区间分成了2 i段，所以答案要加2 i 。

注意d p维护的是下一个位置，所以最后那段是不计算的，要额外再+ 1

代码：

const int maxn=1000000+7;
ll n,m,k,a[maxn],tot[maxn];
ll dp[maxn][25];
ll sum[maxn];
int main(){
  n=read,m=read,k=read;
  rep(i,1,n){
    a[i]=read;
    sum[i]=sum[i-1]+a[i];
    if(a[i]>k) tot[i]=tot[i-1]+1;
    else tot[i]=tot[i-1];
  }
  rep(i,1,n){
    dp[i][0]=upper_bound(sum+1,sum+1+n,sum[i-1]+k)-(sum+1)+1;
  }
  for(int j=1;(1<<j)<n;j++)
    for(int i=1;i+(1<<j)<=n;i++){
      dp[i][j]=dp[dp[i][j-1]][j-1];
    }
  while(m--){
    int l=read,r=read;
    if(tot[r]-tot[l-1]>0){
      puts("Chtholly");
    }
    else{
      int res=1;
      for(int i=20;dp[l][0]<=r;i--)
        if(dp[l][i]&&dp[l][i]<=r)
          l=dp[l][i],res+=(1<<i);
      cout<<res<<endl;
    }
  }
  return 0;
}