这算不算泄题啊。。。被kkk发现会咕咕咕吧。

题目大意：给定一个数列a，与常数n，m，k然后有m个询问，每个询问给定l，r。问在a[l]到a[r]中最少分成几段，使每段的和不超过k，如果无解，输出Chtholly

样例：

input：

5 5 7

2 3 2 3 4

3 3

4 4

5 5

1 5

2 4

output：

1

1

1

2

2

解答：

首先观察数据范围，n<=1e+6 可能的复杂度为O(mlogn).暴力能搞30分吧。

其实这题还是很妙的。我们先考虑暴力：对于[L,R]，设个res，对[l,r]从左往右扫描，将res累加，当res大于k，ans++；当扫描到一个数大于k输出无解

我们可以发现这题是基于贪心的思想，使一个连续子段和尽量大。然后就有点难想了。

您觉得，这道题与树有关系吗?

还真有关系！！记得树的父亲表示法吗？对于n个节点，只要一个序列an即可表示这棵树。

先不考虑无解

对于a[x]我们设ax加到a(y-1)<=k 且ax加到a(y)>k 那么，我们将y当作x的父亲这样就可以弄一颗树

举个栗子：

样例：2 3 2 3 4

k=7 a4是a1的父亲

a4是a2的父亲

a5是a2的父亲

同时设一个root

root是a4的父亲

root是a5的父亲

我们发现，一个点从一个节点转移的另一个节点，等价于在原数列上直接跳过它的最有连续子段。

树上父亲节点的元素编号总是大于儿子

问题转化成：给定树上两点

求较低的点向上走到点p使p的元素编号大于顶一个点需要走几条边。

纯模拟跟暴力复杂度一样O(mn)

其实可以用倍增优化，有点类似于倍增求lca我们设anc[u][i]为u上方2^i个节点

有anc[u][i]=anc[anc[u][i-1]][i-1]

然后再加一个dis数组来存每个点的深度，答案就是一个点跳完后与跳之前的dis之差——差分思想

然后我们再来看如何判无解：

无解是由一种情况有a[i]>k(l<=i<=r)产生的

我们再建树时如果发现a[p]大于k那么就舍弃这个点

最后的树不止有一颗，是个森林。

第一次写博客，不懂可在下方提问。。。。

code：

// luogu-judger-enable-o2#include 
     
      #include 
      
       using namespace std;#define maxn 1000010struct edge{
   int to,nxt;}e[maxn<<1];bool jg[maxn];int fa[maxn],gf[maxn],n,m,k,a[maxn],dis[maxn],anc[maxn][21],head[maxn],pos;void add(int u,int v){e[++pos]=(edge){v,head[u]},head[u]=pos;e[++pos]=(edge){u,head[v]},head[v]=pos;}int ab(int x){
   return x>0 ? x:-x;}void dfs(int u,int ft){    int i;    for(i=head[u];i;i=e[i].nxt){        int v=e[i].to;if(v==ft)continue;        dis[v]=dis[u]+1;        gf[v]=gf[u];        fa[v]=u;        anc[v][0]=u;dfs(v,u);    }}void init(){    int j,i;    for(i=1;i<=n;++i)anc[i][1]=anc[anc[i][0]][0];    for(j=2;j<=20;++j)        for(i=1;i<=n;++i)anc[i][j]=anc[anc[i][j-1]][j-1];}int slove(int x,int y){    int ans=1,i;if(x>y)swap(x,y);    for(i=20;i>=0;--i)    if(anc[x][i]<=y && anc[x][i])    ans+=dis[x]-dis[anc[x][i]],x=anc[x][i];    return ans;}int main(){
   //freopen("in.txt","r",stdin);freopen("o1.txt","w",stdout);    scanf("%d%d%d",&n,&m,&k);int i,j;    for(i=1;i<=n;++i)scanf("%d",&a[i]);a[n+1]=1<<30;    for(i=1;i
       
        k){            jg[i]=1;continue;        }        for(j=i;j<=n+1;++j){            if(a[j]>k){                --j;break;            }            res+=a[j];if(res>k){                --j;break;            }        }        add(i,j+1);    }add(n,n+1);    for(i=n+1;i>0;--i)        if(!gf[i]){            gf[i]=i;dfs(i,-1);        }        init();    while(m--){        int x,y;scanf("%d%d",&x,&y);        if(gf[x]!=gf[y] || jg[x] || jg[y])printf("Chtholly\n");        else {            printf("%d\n",slove(x,y));        }    }}/*5 1 102 5 5 2 5 1 5*/