专栏文章

题解：AT_abc381_e [ABC381E] 11/22 Subsequence

zzhouruoheng
AT_abc381_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir16qj3
此快照首次捕获于
2025/12/04 14:04
3 个月前
此快照最后确认于
2025/12/04 14:04
3 个月前
查看原文
首先处理 1，2，/ 的前缀数量，并记录所有 / 的位置，用 pp 记录。对于 ll 和 rr，找到位于 [l,r][l,r] 的所有 / 的位置。l≤pL≤pR≤rl \le p_{L} \le p_{R} \le r。对于所有 i∈[L,R]i \in [L,R]，设 id=piid=p_i，计算 [l,pi−1][l,p_i-1] 中 1 的数量 c1c1，[pi+1,r][p_i+1,r] 中 22 的数量 c2c2，通过前缀数组记录。显然贡献就是 min⁡(c1,c2)×2+1\min(c1,c2) \times 2 + 1。但是直接枚举 [L,R][L,R] 的话可能会超时，然而实际上这样就能过了 qwq。
记录：https://atcoder.jp/contests/abc381/submissions/60088312
update：更新了两组 hack 数据，把暴力的卡掉了。
考虑优化，i∈[L,R]i \in [L,R]，ii 逐渐增大时，c1c1 单调不减，c2c2 单调不增。而答案是取决于 c1c1 和 c2c2 的最小值。可以用二分解决。
  • 当 c1=c2c1=c2 时，说明答案最大，直接结束。
  • 当 c1<c2c1<c2 时，说明 ii 增加时答案可能更大，L=mid+1L=mid+1。
  • 当 c1>c2c1>c2 时，说明 ii 减小时才回使答案可能更大，R=mid−1R=mid-1。
对于每个 midmid 计算答案。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...