题解：abc370f

atcoder 题解

二分之类的思路就不讲了，这里给点不一样的 check 方法（除了倍增以外的）。

分块

请注意本部分非正解并不能过这道题。

后半部分有一个“往后跳”的过程，考虑维护。

可以联想到一个叫做弹飞绵羊的题。

于是可以考虑分块。

断环为链后分块，记录每个点跳出块所需次数和跳出块后到哪。

令 $A$ 为所有 $\sum a_i$。

复杂度 $O(n\sqrt n log A)$。

但是很惨阿，这样过不了，数据范围不支持，有卡常优化大师卡过去了可以踢我一下。

给出我的愚蠢代码：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define int long long
//NKlogN is easy
//不会倍增，考虑分块
int n,K;
int a[400005];
int sum[400005];
int k[400005],ot[400005],wh[400005],l[400005],r[400005];
int nxt[400005];
int ok[400005];
bool check(int X){
    int j=0;
    for(int i=1;i<=n*2;++i)
    {
        ok[i]=0;
        while(j<=n*2&&sum[j]-sum[i-1]<X)
            ++j;
        nxt[i]=j+1;
        // cerr<<nxt[i]<<" ";
    }
    for(int i=2*n;i>=1;i--){
        if(nxt[i]>r[k[i]]){
            ot[i]=1;//次数
            wh[i]=nxt[i]; 
        }
        else{
            ot[i]=ot[nxt[i]]+1;
            wh[i]=wh[nxt[i]];
        }
    }   
    bool flg=0;
    for(int i=1;i<=n;i++){
        int fr=i,tim=0;
        while(1){
            if(tim+ot[fr]>K){
                // if()
                while(tim<K){
                    if(fr>0 and nxt[fr]<=i+n){
                        fr=nxt[fr];
                    }
                    else{fr=-1;break;}
                    tim++;
                }
                if(fr==-1){
                    ok[i]=0;
                }
                else{
                    ok[i]=flg=1;//cerr<<i<<" ";
                }
                break;
            }
            else if(fr<0){
                break;
            }
            else{
                tim+=ot[fr];
                fr=wh[fr];
            }
            if(fr>n+i) break;
        }
    }
    return flg;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>K;  int sq=sqrt(n*2);
    for(int i=1;i<=n;i++){
        cin>>a[i],a[i+n]=a[i];
    }
    for(int i=1;i<=n*2;i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n*2;i++) l[i]=INT_MAX;
    for(int i=1;i<=n*2;i++){
        k[i]=(i-1)/sq+1;
        l[k[i]]=min(i,l[k[i]]);
        r[k[i]]=i;
    }
    int l=0,r=2000000001,mid,ans;
    while(l<=r){mid=l+r>>1;
        if(check(mid))
            ans=mid,l=mid+1;
        else r=mid-1;
    }
    check(ans);
    cout<<ans<<" ";
    ans=0;
    for(int i=1;i<=n;i++) ans+=!ok[i];
    cout<<ans;
    // for(int i=1;i<=n;i++)cout<<ok[i];
}

带权并查集

此做法能过，并且不需要 $O(nlogn)$ 的空间。

我们处理出每个点对应的 $nxt$（含义同其他题解，双指针求出来满足这一段和大于等于 $mid$ 的下一个点）。顺便记录每个点会从哪些点转移过来。

for(int i=1;i<=n*2;i++)  FR[i].erase(FR[i].begin(),FR[i].end());
    for(int i=1;i<=n*2;++i)
    {   
        tim[i]=0;
        ok[i]=0;
        while(j<n*2&&sum[j]-sum[i-1]<X)
            ++j;
        nxt[i]=j+1;FR[j+1].push_back(i);
    }

然后把所有 $nxt_i \le n$ 的 $i$ 的 $fa$ 设为 $nxt_i$，其余设为自身。$tim_i$ 为 $i$ 跳到他的父亲所需的时间。

for(int i=1;i<=n*2;i++){
        fa[i]=i;
        if(nxt[i]<=n)
            fa[i]=nxt[i],tim[i]=1;
    }

然后循环枚举起点，对于一个新的 $n+i$ 把 $nxt$ 等于他的点的 $fa$ 设为 $i+n$，$tim$ 设为 $1$。

find 就是一个正常的带权并查集的 $find$。

int find(int x){
    if(x==fa[x])
        {return x;}
    int t=find(fa[x]);
    tim[x]+=tim[fa[x]];
    fa[x]=t;
    return fa[x];
}

然后每次 find 一下然后看 $tim_i$ 是不是 $>k$。

就可以了。

for(int i=1;i<=n;i++){
        for(auto V:FR[i+n]){
            fa[V]=i+n;
            tim[V]=1;
        }
        int pos=find(i);
        int tms=tim[i]+1;
        if(tms>K) ok[i]=flg=1;
    }

完整代码：（空间开的有点大）

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define int long long
//NKlogN is easy
//不会倍增，考虑分块
//草，复杂度不对，AC47个点
//考虑奇怪做法
// std::mt19937 rd(time(0));
int n,K;
int a[1000005];
int sum[1000005];
int nxt[1000005];
bool ok[1000005];
int fa[1000005];
int tim[1000005];
int jpt;
vector<int> FR[800005];
int find(int x){
    if(x==fa[x])
        {return x;}
    int t=find(fa[x]);
    tim[x]+=tim[fa[x]];
    fa[x]=t;
    return fa[x];
}
bool check(int X){
    int j=0;
    for(int i=1;i<=n*2;i++)  FR[i].erase(FR[i].begin(),FR[i].end());
    for(int i=1;i<=n*2;++i)
    {   
        tim[i]=0;
        ok[i]=0;
        while(j<n*2&&sum[j]-sum[i-1]<X)
            ++j;
        nxt[i]=j+1;FR[j+1].push_back(i);
    }
    for(int i=1;i<=n*2;i++){
        fa[i]=i;
        if(nxt[i]<=n)
            fa[i]=nxt[i],tim[i]=1;
    }
    bool flg=0;
    for(int i=1;i<=n;i++){
        for(auto V:FR[i+n]){
            fa[V]=i+n;
            tim[V]=1;
        }
        int pos=find(i);
        int tms=tim[i]+1;
        if(tms>K) ok[i]=flg=1;
    }
    return flg;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>a[i],a[i+n]=a[i];
    }
    for(int i=1;i<=n*2;i++){
        sum[i]=sum[i-1]+a[i];
    }
    int l=1,r=2000000001,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))
            ans=mid,l=mid+1;
        else r=mid-1;
    }
    check(ans);
    cout<<ans<<" ";
    ans=0;
    for(int i=1;i<=n;i++) ans+=!ok[i];
    cout<<ans;
}