题解 | 小红的01子序列构造（easy）

枚举左端点然后二分就行了，因为右端点越往右满足的子序列数量单调不减，然后后缀算一下子序列的数量，二分ck的时候减一下就行了

ll dp[N],cnt1[N],cnt0[N];
ll ck(int l,int r){
    return dp[l]-dp[r+1]-((cnt0[l]-cnt0[r+1])*cnt1[r+1]);
}
void solve(){
    ll n,k;
    cin>>n>>k;
    string s;cin>>s;
    s='$'+s;
    for(int i=n;i>=1;i--){
        if(s[i]=='1')dp[i]=dp[i+1];
        else dp[i]=dp[i+1]+cnt1[i+1];
        cnt1[i]=cnt1[i+1]+(s[i]=='1');
        cnt0[i]=cnt0[i+1]+(s[i]=='0');
    }
    for(int i=1;i<=n;i++){
        int L=i+1,R=n,ans=-1;
        while(L<=R){
            int mid=(L+R)>>1;
            if(ck(i,mid)<=k){
                ans=mid;
                L=mid+1;
            }else{
                R=mid-1;
            }
        }
        if(ans!=-1){
            if(ck(i,ans)==k){
                cout<<i<<" "<<ans<<'\n';
                return ;
            }
        }
    }cout<<-1<<'\n';
}