倍增算法——AtCoder Beginner Contest 370 F

F - Cake Division

题意：就是说给你一个蛋糕，然后又n块，让你分成k份，每份蛋糕必须要相连，然后问你所有分的情况中，最小的那一份蛋糕，最大的质量是多少，然后判断，在每一种划分中，都不会被划分到的那条线有几条

思路：首先，这是一个环，很明显，我们要将环拆分为链，因此我们在原数组的后面再接上长度为n的数组一次即可

然后我们要分成k份，因此我们要遍历每一个点，总共n个，还要进行二分去找每一个点的最右的一个端点，时间复杂度为n^2logn,很明显会超时，那么我们该如何去优化？

我们可以考虑倍增算法，可以通过O(n)的滑动窗口得到最右端的位置。这就是分一段的区间，而如果分两段就f[f[x]]。注意到只要起点固定，它会延伸到哪里也固定了，不同段之间也相互独立。因此函数可以简单的复合起来，相比于一次一次分，优化方向就是以倍增的形式分段。

二分之后用倍增去处理每一个点分2^j段的最右边界，这样时间复杂度为nlogn^2这样时间就过了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int a[400005];
int f[400005][20];
deque<int> que;int check(int mid)
{f[2*n][0]=2*n+1;f[2*n+1][0]=2*n+1;int r=1,sum=0;for(int i=1;i<=2*n;i++){while(sum<mid&&r<=2*n){que.push_back(a[r]);sum+=a[r];r++;}if(sum>=mid){f[i][0]=r;}else{f[i][0]=2*n+1;}sum-=que.front();que.pop_front();}for(int j=1;j<20;j++){for(int i=1;i<=2*n+2;i++){f[i][j]=f[f[i][j-1]][j-1];}}int flag=0;int cnt=0;for(int i=1;i<=n;i++){int p=i;for(int j=19;j>=0;j--){if((k>>j)&1){p=f[p][j];}}if(p<=i+n){cnt++;}}return cnt;
}int find()
{int cnt=0;for(int i=1;i<=n;i++){int p=i;for(int j=20;j>=0;j--){if((k>>j)&1){p=f[p][j];}}if(p<=i+n){cnt++;}}return cnt; 
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}int l=1,r=1e12;int ans=0;while(l<=r){int mid=(l+r)/2;if(check(mid)){ans=mid;l=mid+1;}else{r=mid-1;}}int cnt=check(ans);cout<<ans<<" "<<n-cnt<<"\n";return 0;
}