https://www.nowcoder.com/practice/3647d44e120b4ec19536a8236d251a06?tpId=182&tqId=46507&rp=1&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page&difficulty=undefined&judgeStatus=undefined&tags=&title=

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int M = 3e5 + 5, mod = 998244353;
int a[M];
struct dian
{
    int l, r, lw, rw, sum;
    // lw表示左边连续的1的个数
    // rw表示右边连续的1的个数
    // sum表示区间每段连续1除2向上取整的和
} f[M << 2];
dian merge(dian x, dian y)
{
    int c1 = x.lw, c2 = x.rw;
    int c3 = y.lw, c4 = y.rw;
    int flag1 = 0, flag2 = 0;
    if (c1 == x.r - x.l + 1)
        flag1 = 1;
    if (c3 == y.r - y.l + 1)
        flag2 = 1;
    int id = 0;
    dian ans;
    ans.l = x.l;
    ans.r = y.r;
    // 如果左子树全为1，右子树不为1，则将左边连续的1的个数加到右子树的左边
    if (flag1 == 1 && flag2 == 0)
    {
        ans.lw = c1 + c3;
        ans.rw = c4;
        ans.sum = (c1 + c3 + 1) / 2 - (c3 + 1) / 2 + y.sum;
        return ans;
    }
    if (flag1 == 0 && flag2 == 1)
    {
        ans.lw = c1;
        ans.rw = c2 + c4;
        ans.sum = (c2 + c4 + 1) / 2 - (c2 + 1) / 2 + x.sum;
        return ans;
    }
    if (flag1 == 0 && flag2 == 0)
    {
        ans.lw = c1;
        ans.rw = c4;
        ans.sum = x.sum + y.sum - (c2 + 1) / 2 - (c3 + 1) / 2 + (c2 + c3 + 1) / 2;
        return ans;
    }
    ans.lw = c1 + c3;
    ans.rw = c2 + c4;
    ans.sum = (c1 + c3 + 1) / 2;
    return ans;
}
void pushup(int id)
{
    f[id] = merge(f[id << 1], f[id << 1 | 1]);
}
void build(int id, int l, int r)
{
    f[id].l = l, f[id].r = r;
    if (l == r)
    {
        f[id].lw = f[id].rw = a[l];
        f[id].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
dian query(int id, int l, int r)
{
    if (l <= f[id].l && f[id].r <= r)
        return f[id];
    int mid = (f[id].l + f[id].r) >> 1;
    if (r <= mid)
        return query(id << 1, l, r);
    if (l > mid)
        return query(id << 1 | 1, l, r);
    dian x = query(id << 1, l, r);
    dian y = query(id << 1 | 1, l, r);
    return merge(x, y);
}
void solve()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> sum(n + 2);
    for (int i = 1; i <= n; i++)
    {
        a[i] = s[i - 1] - '0';
        sum[i] = sum[i - 1] + (a[i] == 0);
    }
    build(1, 1, n);
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        dian ans = query(1, l, r);
        cout << ans.sum + (sum[r] - sum[l - 1]) << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}