Submission #75818914

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char a[300030];
ll chk[300030], sum[300030];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll n,q;
    cin>>n>>q;
    for (ll i=1;i<=n;i++) cin>>a[i];
    vector<ll> en, st;
    for (ll i=1;i<=n-1;i++)
    {
        if (a[i]!=a[i+1]&&a[i]!='X') en.push_back(i);
    }
    if (a[n]!='X') en.push_back(n);
    for (ll i=n;i>=2;i--)
    {
        if (a[i]!=a[i-1]&&a[i]!='X') st.push_back(i);
    }
    if (a[1]!='X') st.push_back(1);
    reverse(st.begin(),st.end());
    for (ll i=2;i<=n;i++)
    {
        if (a[i]==a[i-1]&&a[i]!='X'&&chk[i-1]==0)
        {
            chk[i]=1;
            sum[i]=1;
        }
    }
    for (ll i=1;i<=n;i++) sum[i]=sum[i-1]+sum[i];
    for (ll i=1;i<=q;i++)
    {
        ll ans=0;
        ll l,r;
        cin>>l>>r;
        ll idx1, idx2;
        if (a[l]=='X') idx1 = l;
        else idx1 = *lower_bound(en.begin(),en.end(),l);
        if (idx1>=r)
        {
            cout<<(r-l+1)/2<<"\n";
            continue;
        }
        if (a[r]=='X') idx2=r;
        else idx2 = *prev(upper_bound(st.begin(),st.end(),r));
        ans+=(idx1-l+1)/2+(r-idx2+1)/2;
        ans+=sum[idx2-1]-sum[idx1];
        cout<<ans<<"\n";
    }
}

Submission Info

Judge Result