题目链接
题目大意
给定一个长度为 (N) 的序列 (A) 和一个常数 (K)
有 (M) 次询问
每次询问查询一个区间 ([L , R]) 内所有数最少分成多少个连续段
使得每段的和都 (<= K) ,若无解则输出 "(Chtholly)"
解题思路
简单回忆一下倍增求 (LCA) 思想:
- (f[i][j]) 表示以 (i) 为起点,往上跳 (i + 2^j) 步后得到的祖先
- 因为往上跳 (2^j) 等价于先往上跳 (2^{j - 1}) 步后再往上跳 (2^{j - 1}) 步
- 所以可得: (f[i][j] = f[f[i][j - 1]][j - 1])
回到这道题:
暴力的做法即遍历区间 ([l,r]) ,贪心的让每段的长度尽可能大
考虑用倍增思想优化:
定义 (f[i][j]) 表示:
以 (i) 为起点,分成 (2 ^ j) 个连续段后,所能到达的最远位置的下一个位置(其中每个段的和都不超过 (K))
那么不难得到: (f[i][j] = f[f[i][j - 1]][j - 1]) ((f[i][0]) 可通过二分前缀和得到
然后对于每个询问 ((L , R)):
先判断区间 ([L,R]) 是否存在 (A_i) 使得 (A_i > K)
这步我们维护一个权值数组的前缀和 (O1) 判断
即当 (A_i <= K) 时,(sum[i] = sum[i - 1])
当 (A_i > K)时,(sum[i] = sum[i - 1] + 1)
当 (sum[R] - sum[L - 1] > 0) 则表示该区间存在 (A_i > K),直接输出 (Chtholly)
若 (sum[R] - sum[L - 1] = 0) 则从高位往低位枚举 (j):
如果 (f[L][j] > R) 则表示从 (L) 开始划分出 (2^j) 个连续段是 (OK) 的
但是 (2^j) 连续段可能太多了(题目要求划分的连续段个数最少
所以就继续往下枚举如果 (f[L][j] < R),则表示从 (L) 开始划分出 (2^j) 个连续段是不够的
那就先划分出 (2^j) 个连续段,然后再从 (f[L][j]) 的位置继续划分
即 (ans += 1 << j) ,(L = f[L][j])
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int f[N][22];
int n , m , k , a[N] , sum[N];
long long pre[N];
signed main()
{
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; i ++)
{
cin >> a[i] , pre[i] = pre[i - 1] + a[i];
sum[i] = sum[i - 1] + (a[i] > k);
}
for(int j = 0 ; j <= 21 ; j ++) f[n + 1][j] = n + 1;
for(int j = 0 ; j <= 21 ; j ++)
{
for(int i = 1 ; i <= n ; i ++)
{
f[i][0] = upper_bound(pre + i , pre + 1 + n , k - a[i] + pre[i]) - pre;
if(!j) continue ;
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
while(m --)
{
int l , r , ans = 0;
cin >> l >> r;
if(sum[r] - sum[l - 1])
{
cout << "Chtholly
";
continue ;
}
for(int j = 21 ; j >= 0 ; j --)
{
if(f[l][j] - 1 < r)
{
ans += 1 << j;
l = f[l][j];
}
}
cout << ans + 1 << '
';
}
return 0;
}