[DP 倍增]区间的连续段

[DP 倍增]区间的连续段

题目

​​题目链接​​

思路

题意：
给你长度为n的数组，由m次查询，每次查询问对于区间[l,r]，最少把区间内数切成几段，使得每一段满足和都<=k。

个人学习记录使用，​​参考这里的第一篇题解​​

数据范围很大，暴力必T
对于100%的数据，1 <= n , m <= 1000000 , 1 <= ai , k <= 1000000000

然后照着题解学了一下倍增优化

1预处理除前缀和

2然后对倍增DP数组做预处理

表示从i开始分成段，能走到最远的位置的下一个位置

①

②就是第i个位置能走到最远的位置，这个可以用二分upper_bound预处理出满足条件最后一个位置的下一个位置，这个可以转化为查找第一个的位置

3倍增DP状态转移

4查询

反向遍历j

如果从i开始分成段能到达的最远位置

如果比r大，减小i

如果<=r，增加答案，更新左端点

5检验

如果查询到最后表示还有答案的，因为要到f[l][0]才会>k啊
如果表示没有答案，注意这里包含<=，因为定义的是满足条件的下一个位置

代码

// Problem: 区间的连续段
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/15429
// Memory Limit: 524288 MB
// Time Limit: 14000 ms
// FishingRod

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY
n 1 1e6
m 1 1e6
ai 1 1e9
k 1 1e9
*/
int T;
LL n,m,k;
const int N=1e6+10;
LL a[N],pre[N],f[N][22];
void solve(int C)
{
  //NEW DATA CLEAN
  
  //NOTE!!!
  scanf("%lld %lld %lld",&n,&m,&k);
  for(int i=1;i<=n;i++)
  {
    scanf("%lld",&a[i]);
    pre[i]=pre[i-1]+a[i];//处理前缀和
  }
  for(int i=0;i<=21;i++)f[n+1][i]=n+1;//第一个预处理
  for(int i=n;i>=1;i--)
  {
    f[i][0]=upper_bound(pre+i,pre+n+1,pre[i-1]+k)-pre;//第二个预处理
    for(int j=1;j<=21;j++)
      f[i][j]=f[f[i][j-1]][j-1];
  }
  while(m--)
  {
    int l,r,ans=0;
    scanf("%d %d",&l,&r);
    for(int i=21;i>=0;i--)
    {
      if(f[l][i]<=r)ans+=1<<i,l=f[l][i];
    }
    if(f[l][0]>r)printf("%d\n",ans+1);
    else printf("Chtholly\n");
  }
}

int main()
{
  #ifdef MULINPUT
    scanf("%d",&T);
    for(int i=1;i<=T;i++)solve(i);
  #else
    solve(1);
  #endif
  return 0;
}