这算不算泄题啊。。。被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 <cstdio>
#include <algorithm>
using namespace std;
#define maxn 1000010
];
bool jg[maxn];
],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;}
? 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]+;
gf[v]=gf[u];
fa[v]=u;
anc[v][]=u;dfs(v,u);
}
}
void init(){
int j,i;
;i<=n;++i)anc[i][]=anc[anc[i][]][];
;j<=;++j)
;i<=n;++i)anc[i][j]=anc[anc[i][j-]][j-];
}
int slove(int x,int y){
,i;if(x>y)swap(x,y);
;i>=;--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;
;i<=n;++i)scanf(]=<<;
;i<n;++i){
;if(a[i]>k){
jg[i]=;continue;
}
;++j){
if(a[j]>k){
--j;break;
}
res+=a[j];if(res>k){
--j;break;
}
}
add(i,j+);
}add(n,n+);
;i>;--i)
if(!gf[i]){
gf[i]=i;dfs(i,-);
}
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 10
2 5 5 2 5
1 5
*/