更加进阶一些的好像是树状数组+二分？

在最近的练习中经常遇到能用二分+前缀和的套路能解决的问题，这里记录一下；

牛客训练营的 R

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;;
pair<int,int> q[N];
int mm,last;
int n,k,res;
char s[N];
int sum[N];
signed main(){
    cin>>n>>k;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+(s[i]=='R');
        if(s[i]!='P') continue;
        q[mm++]={last,i};
        last=i;
    }
    q[mm++]={last,n+1};
    for(int i=0;i<mm;i++){
        int L=q[i].first,R=q[i].second;
        for(int j=L+1;j<R;j++){
            int l=j,r=R-1;
            if(sum[r]-sum[l-1]<k) break;
            int p=lower_bound(sum+1,sum+1+n,sum[l-1]+k)-sum;
            res+=R-p;
        }
    }
    cout<<res;
}

cf上也有类似的题目
C. Hard Process
也许这就是edu场的含义？

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,k;
int res;
pair<int,int> q;
int a[N],sum[N],ans[N];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=a[i]+sum[i-1];
        ans[i]=ans[i-1]+1-a[i];
    }
    for(int i=1;i<=n;i++){
        int l=i,r=n;
        int p=lower_bound(ans+1,ans+1+n,ans[i-1]+k)-ans;
        if(ans[n]-ans[i-1]<k){
            if(res<n+1-i)
            q={i,n};
            res=max(n+1-i,res);
        }else if(k>=ans[p]-ans[i-1]&&p>=i-1){
            p++;
            while(p<=n&&a[p]==1) p++;
            p--;
            if(res<p+1-i)
            q={i,p};
            res=max(res,p+1-i);
        }
    }
    cout<<res<<endl;
    for(int i=1;i<=n;i++){
        if(i>=q.first&&i<=q.second) cout<<"1 ";
        else cout<<a[i]<<' ';
    }
}

还有牛客第三场的智乃的密码也是一类问题
挂个link