Submission #75816888

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define MOD 1000000007
#define INF 987654321
#define PI 3.1415926535

int len;
int tree[300001];

int sum(int k)
{
    int s = 0;
    while (k >= 1)
    {
        s += tree[k];
        k -= k & -k;
    }
    return s;
}

void add(int k, int x)
{
    while (k <= len)
    {
        tree[k] += x;
        k += k & -k;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    vector<int> v;
    int cur = 1;
    for (int i = 1; i < n; i++)
    {
        if (s[i] != 'X' && s[i] == s[i - 1])
        {
            cur++;
        }
        else
        {
            v.push_back(cur);
            cur = 1;
        }
    }
    v.push_back(cur);

    len = v.size();
    for (int i = 0; i < len; i++)
    {
        add(i + 1, v[i] / 2);
    }

    for (int i = 1; i < len; i++)
    {
        v[i] += v[i - 1];
    }

    while (q--)
    {
        int l, r;
        cin >> l >> r;

        int ans = 0;

        int vl = lower_bound(v.begin(), v.end(), l) - v.begin();
        int vr = lower_bound(v.begin(), v.end(), r) - v.begin();

        if (vl == vr)
        {
            ans += (r - l + 1) / 2;
        }
        else
        {
            ans += (v[vl] - l + 1) / 2;
            ans += (r - v[vr - 1]) / 2;
        }

        if (vl + 1 <= vr - 1)
        {
            ans += (sum(vr) - sum(vl + 1));
        }

        cout << ans << '\n';
    }
}

Submission Info

Judge Result