首先考虑最暴力的做法。那复杂度是q * range的显然会爆。
原本我是想用什么数据结构优化这个过程，但是想了想好像没什么东西处理划分这个操作。
于是考虑观察这个操作的性质，我们发现对于每个范围，一旦L确定那么，在[L, R] 之间的划分数其实是固定的。（但是划分方案可能会有很多种）
这里可以稍稍证明一下：
假设区间为[L, R]，那么最多的划分数就是R-L+1，之后我们为了尽可能减少划分数，我们必然要尽可能让一个划分集合与左右两边的集合合并。
于是我们就利用贪心的思想，尽量让每一个划分集合都尽量大，那么我们就能做到划分数最小。
于是我们解决了第一步，如何处理划分数的问题。但是我们不能通过预处理 divide_num[L][R]这个二维数组去得到答案。
于是考虑优化掉数组第二维，该如何快速知道在L确定的情况下，到R的划分数呢？
我们发现，最最开始，我们的划分数组存的其实都是到下一个划分点的位置，我们每次可以通过跳跃，去获得下一个划分点的位置，从而获得答案。
但是最坏情况下就是，这个跳跃数都为1，即每个a[i] + a[i+1] > k， a[i] <= k。这样的话就会被卡成n2了。我们发现这个跳跃操作，其实是可以被优化的。
考虑到跟树上倍增一样的思想，每次跳2的幂次，这样的话我们的复杂度就被降低到nlogn了。
于是开始写。
代码如下：
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; ///1061109567 const int maxn = 2e6 + 10; int n, m, k; ll sum[maxn], a[maxn]; int f[maxn][30], cant[maxn]; int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++ i) { scanf("%lld", &a[i]); sum[i] = a[i] + sum[i-1]; cant[i] = cant[i-1] + (a[i] > k); } for (int j = 0; j <= 20; ++ j) { for (int i = 1; i <= n; ++ i) { if (j == 0) { int pos = upper_bound(sum+1, sum+1+n, sum[i-1]+k) - sum; f[i][j] = pos; //cout << "pos: " << pos << endl; } else f[i][j] = f[f[i][j-1]][j-1]; } } while (m--) { int l, r; scanf("%d%d", &l, &r); if (cant[r] - cant[l-1] > 0) { puts("Chtholly"); continue; } int ans = 1; ///至于ans为什么一开始是1，是因为我们记录的都是下一个划分数的位置， ///并且在寻找答案的时候让下一个划分数的位置<=R这说明最后一条我们是没有算在答案里面的， ///所以需要+1。 for (int j = 20; j >= 0; -- j) { ///f[l][j] != 0的原因是因为l + 1<<j会大于n， ///这样的话倍增数组其实是没有给值的此时为0 ///0 <= r 但是我们又不希望访问越界的位置。所以需要!=0 if (f[l][j] && f[l][j] <= r) { l = f[l][j]; ans += (1 << j); } } // puts(""); printf("%d ", ans); } return 0; }