社区讨论
ABC 的 E 二分答案哪儿有问题
学术版参与者 4已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @m3st73e9
- 此快照首次捕获于
- 2024/11/22 22:00 去年
- 此快照最后确认于
- 2025/11/04 14:10 4 个月前
CPP
#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
int n,T,s1[N],s2[N],ans,L,R,a[N],tot,ll,rr;
string s;
bool check(int x){
if(s1[R]-s1[L-1]<x||s2[R]-s2[L-1]<x) return false;
int l=L,r=R,mid,tmp;
while(l<r){
mid=l+r>>1;
if(s1[mid]-s1[L-1]>=x) r=mid;
else l=mid+1;
}tmp=l,l=L,r=R;
while(l<r){
mid=l+r+1>>1;
if(s2[R]-s2[mid-1]>=x) l=mid;
else r=mid-1;
}
ll=lower_bound(a+1,a+tot+1,tmp)-a;
rr=upper_bound(a+1,a+tot+1,l)-a-1;
return ll<=rr;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>T>>s,s=" "+s;
for(int i=1;i<=n;i++){
s1[i]=s1[i-1]+(s[i]=='1');
s2[i]=s2[i-1]+(s[i]=='2');
}
for(int i=1;i<=n;i++){
if(s[i]=='/') a[++tot]=i;
}
while(T--){
cin>>L>>R;
int l=-1,r=R,mid;
while(l<r){
mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
if(l==-1) cout<<0<<endl;
else cout<<l*2+1<<endl;
}
return 0;
}
/*
14 1000
111111222221/2
4 13
*/
最后使用普通二分过的()
回复
共 8 条回复,欢迎继续交流。
正在加载回复...