Ниже — решение за $O(n + q)$.

Идея

1. Подстрока $s_l,\dots,s_r$ задаёт число

   $$S = \sum_{i=l}^{r} s_i \cdot 2^{i-l} \pmod 3.$$

   Так как $2^k \equiv (-1)^k \pmod 3$, то вес бита зависит только от чётности $(i-l)$:

   • если $i$ и $l$ одной чётности — вес $1$,
   • если разной — вес $2$.

   Поэтому нам нужны только количества единиц на позициях той же чётности, что $l$, и другой чётности.

2. Эффект перестановки соседних битов $s_k$ и $s_{k+1}$ на сумму:

   • если $s_k = s_{k+1}$, то ничего не меняется (∆ = 0);
   • если $(s_k,s_{k+1}) = (1,0)$ или $(0,1)$, то ∆ = ±$2^{k-l}$ ≡ 1 или 2 (в зависимости от чётности $k-l$ и порядка битов).

   Итог:

   • пары с равными битами никогда не меняют делимость (∆ = 0),
   • пары с разными битами дают ∆ = 1 или 2 по фиксированной схеме.

3. Для подстроки:

   • пусть $S$ — её значение по модулю 3;
   • хотим, чтобы после перестановки $S' = S + \Delta \equiv 0$;
   • значит $\Delta \equiv -S \pmod 3$.

   Тогда:

   • если $S = 0$: нужны пары с $\Delta = 0$, т.е. все соседние равные биты внутри $[l, r]$;
   • если $S = 1$: нужна $\Delta = 2$;
   • если $S = 2$: нужна $\Delta = 1$.

4. Проблема: $\Delta$ зависит от:

   • пары битов (01 или 10),
   • чётности позиции $k$,
   • чётности левой границы $l$.

   Поэтому заранее для каждой позиции пары $k$ (между $k$ и $k+1$) посчитаем, какую ∆ она даёт:

   • если $l$ чётное,
   • если $l$ нечётное.

   Сделаем 5 массивов по парам:

   • eq[k] — 1, если $s_k = s_{k+1}$,
   • d0_1[k] — 1, если при чётном l эта пара даёт ∆ = 1,
   • d0_2[k] — ∆ = 2 при чётном l,
   • d1_1[k] — ∆ = 1 при нечётном l,
   • d1_2[k] — ∆ = 2 при нечётном l.

   По ним считаем префиксные суммы и отвечаем на запрос за $O(1)$.

5. Значение подстроки $S \pmod 3$:

   Предварительно считаем префиксы:

   • preOdd[i] — число единиц на нечётных позициях ≤ i,
   • preEven[i] — число единиц на чётных позициях ≤ i.

   Для запроса $[l, r]$:

   • onesOdd = preOdd[r] - preOdd[l-1],
   • onesEven = preEven[r] - preEven[l-1].
   • если l нечётное:
     • биты той же чётности: same = onesOdd,
     • другой чётности: diff = onesEven;
   • если l чётное — наоборот.

   Тогда

   $$S \equiv \text{same} + 2 \cdot \text{diff} \pmod 3.$$

Код на C++

cpp
#include <bits/stdc++.h>
using namespace std;

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

    string s;
    if (!(cin >> s)) return 0;
    int n = (int)s.size();

    // Сделаем 1-индексацию строки
    string t = " " + s;

    // Префиксы количества единиц на чётных и нечётных позициях
    vector<int> preOdd(n + 1, 0), preEven(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        preOdd[i] = preOdd[i - 1];
        preEven[i] = preEven[i - 1];
        if (t[i] == '1') {
            if (i & 1) preOdd[i]++;
            else preEven[i]++;
        }
    }

    // Массивы по парам (между i и i+1), и их префиксы
    vector<int> pref_eq(n + 1, 0);
    vector<int> pref_d0_1(n + 1, 0), pref_d0_2(n + 1, 0);
    vector<int> pref_d1_1(n + 1, 0), pref_d1_2(n + 1, 0);

    for (int i = 1; i < n; ++i) {
        int eq = 0, d01 = 0, d02 = 0, d11 = 0, d12 = 0;
        char a = t[i], b = t[i + 1];
        if (a == b) {
            // Равные биты: ∆ = 0 всегда
            eq = 1;
        } else {
            int pk = i & 1; // 0 - чётный, 1 - нечётный индекс k
            bool is10 = (a == '1' && b == '0');
            if (is10) {
                // Пара "10": ∆ = 1, если pk == pl, иначе 2
                // pl = 0 (l чётное)
                if (pk == 0) d01 = 1;
                else d02 = 1;
                // pl = 1 (l нечётное)
                if (pk == 1) d11 = 1;
                else d12 = 1;
            } else {
                // Пара "01": ∆ = 2, если pk == pl, иначе 1
                // pl = 0
                if (pk == 0) d02 = 1;
                else d01 = 1;
                // pl = 1
                if (pk == 1) d12 = 1;
                else d11 = 1;
            }
        }

        pref_eq[i]     = pref_eq[i - 1]     + eq;
        pref_d0_1[i]   = pref_d0_1[i - 1]   + d01;
        pref_d0_2[i]   = pref_d0_2[i - 1]   + d02;
        pref_d1_1[i]   = pref_d1_1[i - 1]   + d11;
        pref_d1_2[i]   = pref_d1_2[i - 1]   + d12;
    }

    // Для удобства продублируем последний элемент, хотя не обязательно
    pref_eq[n]   = pref_eq[n - 1];
    pref_d0_1[n] = pref_d0_1[n - 1];
    pref_d0_2[n] = pref_d0_2[n - 1];
    pref_d1_1[n] = pref_d1_1[n - 1];
    pref_d1_2[n] = pref_d1_2[n - 1];

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

        // считаем S(l, r) mod 3
        int onesOdd  = preOdd[r]  - preOdd[l - 1];
        int onesEven = preEven[r] - preEven[l - 1];

        int pl = l & 1;
        int samePar, diffPar;
        if (pl == 1) {
            samePar = onesOdd;
            diffPar = onesEven;
        } else {
            samePar = onesEven;
            diffPar = onesOdd;
        }

        int S = (samePar + 2 * diffPar) % 3;

        int ans = 0;
        if (S == 0) {
            // Нужны пары с ∆ = 0 — это все равные пары
            ans = pref_eq[r - 1] - pref_eq[l - 1];
        } else {
            int target = (3 - S) % 3; // либо 1, либо 2
            if (pl == 0) {
                // l чётное
                if (target == 1)
                    ans = pref_d0_1[r - 1] - pref_d0_1[l - 1];
                else
                    ans = pref_d0_2[r - 1] - pref_d0_2[l - 1];
            } else {
                // l нечётное
                if (target == 1)
                    ans = pref_d1_1[r - 1] - pref_d1_1[l - 1];
                else
                    ans = pref_d1_2[r - 1] - pref_d1_2[l - 1];
            }
        }

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

    return 0;
}

Если хочешь, могу ещё дорисовать картинку/табличку с типами пар и их вкладом ∆ в зависимости от чётности l и k.