社区讨论

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 条回复,欢迎继续交流。

正在加载回复...