ABC-381-E - 11/22 Subsequence · znzryb
## 思路讲解
需要动点脑子的二分，调了比较久
我的方法就是跑两遍二分，这样避免有情况漏考虑
`跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能`
```cpp
while(l<r){
ll x=l+r+1>>1;
ll cnt1=freq1[pos[x]]-freq1[down-1];
ll cnt2=freq2[up]-freq2[pos[x]]; //这里不用减1
ans=max(min(cnt1,cnt2)*2+1,ans);
if(cnt1==cnt2){
cout<< ans <<endl;
return;
}
if(cnt1<cnt2){
l=x;
}else{
r=x-1;
}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
// 跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能
// 下面一个二分与他互补
l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
while(l<r){
ll x=l+r>>1;
ll cnt1=freq1[pos[x]]-freq1[down-1];
ll cnt2=freq2[up]-freq2[pos[x]]; //这里不用减1
ans=max(min(cnt1,cnt2)*2+1,ans);
if(cnt1==cnt2){
cout<< ans <<endl;
return;
}
if(cnt1<cnt2){
l=x+1;
}else{
r=x;
}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
```
当然一些常见的优化自不必多说
## AC代码
[https://atcoder.jp/contests/abc381/submissions/61320459](https://atcoder.jp/contests/abc381/submissions/61320459)
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10;
ll n,T;
char s[N];
ll freq1[N],freq2[N];
vector<ll> pos; // /的位置
ll down=0,up=0;
ll ans;
void solve(){
cin>>down>>up;
// 二分
ll l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
if(pos[l]>up || l==pos.size()){// 防止pos[l]超界(以这种方法找出来的l都超界，那必然没/在里面)
cout<<0<<endl;
return;
}
ll r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
// 避免起始l==r导致WA
ans=min(freq1[pos[l+r>>1]]-freq1[down-1],freq2[up]-freq2[pos[l+r>>1]])*2+1;
while(l<r){
ll x=l+r+1>>1;
ll cnt1=freq1[pos[x]]-freq1[down-1];
ll cnt2=freq2[up]-freq2[pos[x]]; //这里不用减1
ans=max(min(cnt1,cnt2)*2+1,ans);
if(cnt1==cnt2){
cout<< ans <<endl;
return;
}
if(cnt1<cnt2){
l=x;
}else{
r=x-1;
}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
// 跑两遍二分，因为上面的二分相当于否决了r=x-1是最优解的可能
// 下面一个二分与他互补
l=lower_bound(pos.begin(), pos.end(), down)-pos.begin();
r=upper_bound(pos.begin(), pos.end(), up)-pos.begin()-1;
while(l<r){
ll x=l+r>>1;
ll cnt1=freq1[pos[x]]-freq1[down-1];
ll cnt2=freq2[up]-freq2[pos[x]]; //这里不用减1
ans=max(min(cnt1,cnt2)*2+1,ans);
if(cnt1==cnt2){
cout<< ans <<endl;
return;
}
if(cnt1<cnt2){
l=x+1;
}else{
r=x;
}
}
ans=max(min(freq1[pos[l]]-freq1[down-1],freq2[up]-freq2[pos[l]]),ans);
cout<< ans <<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>T;
for(int i=1;i<=n;++i)
cin>>s[i];
ll cnt1l =0,cnt2l=0;
for(int i=1;i<=n;++i){
if(s[i]=='1')
cnt1l+=1;
else if(s[i]=='2')
cnt2l+=1;
else
pos.push_back(i);
freq1[i]=cnt1l;
freq2[i]=cnt2l;
}
while (T--) {
if(pos.empty()){
cout<<0<<endl;
continue;
}
solve();
}
return 0;
}
/*
50 10
/211//2///1212/212/12/12/1//11111/12121//22/122221
16 19
27 45
12 32
45 49
33 42
7 9
18 46
1 5
44 45
3 23
*/
```
## 心路历程（WA，TLE，MLE……）