题解：AT_abc381_e [ABC381E] 11/22 Subsequence

zhouruoheng · 2024-11-23 13:07:33 · 题解

首先处理 1，2，/ 的前缀数量，并记录所有 / 的位置，用 p 记录。对于 l 和 r，找到位于 [l,r] 的所有 / 的位置。l \le p_{L} \le p_{R} \le r。对于所有 i \in [L,R]，设 id=p_i，计算 [l,p_i-1] 中 1 的数量 c1，[p_i+1,r] 中 2 的数量 c2，通过前缀数组记录。显然贡献就是 \min(c1,c2) \times 2 + 1。但是直接枚举 [L,R] 的话可能会超时，然而实际上这样就能过了 qwq。

记录：https://atcoder.jp/contests/abc381/submissions/60088312

update：更新了两组 hack 数据，把暴力的卡掉了。

考虑优化，i \in [L,R]，i 逐渐增大时，c1 单调不减，c2 单调不增。而答案是取决于 c1 和 c2 的最小值。可以用二分解决。

• 当 c1=c2 时，说明答案最大，直接结束。
• 当 c1<c2 时，说明 i 增加时答案可能更大，L=mid+1。
• 当 c1>c2 时，说明 i 减小时才回使答案可能更大，R=mid-1。

对于每个 mid 计算答案。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,q;
string s;
int a[N],b[N],c[N];
int p[N],tot;
void solve()
{
    cin>>n>>q;
    cin>>s;
    s="0"+s;
    for(int i=1;i<=n;i++) 
    {
        if(s[i]=='1') a[i]=1;
        else if(s[i]=='2') b[i]=1;
        else 
        {
            c[i]=1;
            p[++tot]=i;
        }
        a[i]+=a[i-1];
        b[i]+=b[i-1];
        c[i]+=c[i-1];
    }
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        int L=lower_bound(p+1,p+tot+1,l)-p;
        int R=upper_bound(p+1,p+tot+1,r)-p-1;
        int ans=0;
        int mid,c1,c2,id;
        while(L<=R)
        {
            mid=L+R>>1;
            id=p[mid];
            c1=a[id-1]-a[l-1];
            c2=b[r]-b[id];
            ans=max(ans,2*min(c1,c2)+1);
            if(c1<c2) L=mid+1;
            else if(c1>c2) R=mid-1;
            else break;
        }
        cout<<ans<<'\n';
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}