NC82B

题意

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

思路

预处理前缀和 ST表
分两种情况考虑：

输出" $Chtholly$ " ，这种情况 $a_i>k$ ，用ans数组维护是否 $[L,R]$ 范围内存在 $a_i>k$ 的情况。
输出 $[L,R]$ 范围内所有数最少分成多少个连续段。首先预处理计算前缀和，利用二分查找前缀和的方式初始化 $st[i][0]$ ， $st[i][j]$ 表示从第 $i$ 个位置开始分 $2^j$ 段，最多能到第几个位置。

注意点：

倍增跳跃的时候选择从大到小开始遍历，能跳大的且不超过R的时候先跳大的。
例如5=4+1如果从小的开始找就会出现5!=1+2+4然后回溯在到5=1+4所以要倒着来。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 10;

ll n,m,k,a[maxn],st[maxn][21],pre[maxn],ans[maxn];

void getst(){
    for(int i=1;i<=n;i++)
        st[i][0]=upper_bound(pre+1,pre+1+n,pre[i-1]+k)-pre;
    for(int i=1;(1<<i)<n;i++)
        for(int j=1;j+(1<<i)<=n;j++)
            st[j][i]=st[st[j][i-1]][i-1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
        ans[i]=ans[i-1]+(a[i]>k);
    }
    getst();
    while(m--){
        int L,R,res=1;
        cin>>L>>R;
        if(ans[R]-ans[L-1]>0){
            cout<<"Chtholly\n";
        }else{
        //这里注意要从大的开始跳，一个数总能从大的开始表示二进制，从小的开始可能会出现回溯
        //例如5=4+1如果从小的开始找就会出现5!=1+2+4然后回溯在到5=1+4所以要倒着来
            for(int i=20;st[L][0]<=R;i--)
                if(st[L][i]&&st[L][i]<=R)//这里之所以st[L][i]要非0，是因为如果从L跳2^i超过了R，则st[L][i]却为0的情况
                    L=st[L][i],res+=(1<<i);
            cout<<res<<'\n';
        }
    }
    return 0;
}