AC代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
#ifndef ONLINE_JUDGE
#include "test.h"
#else
#define debug(...) 42
#define debug_assert(...) 42

#endif
i64 dis1(int l, int r, int n, vector<pair<i64, i64> > &mp, vector<vector<i64> > &node) {
    if (l >= n) l -= n;
    if (r >= n) r -= n;
    if (mp[l].first != mp[r].first) return -1;
    i64 ll = mp[l].second, rr = mp[r].second;
    if (ll > rr) {
        ll -= node[mp[l].first].size();
    }
    return (rr - ll) * n;
}

i64 get_w(int l, int r, vector<i64> &w) {
    if (l > r) return 0;
    if (l == 0) return w[r];
    return w[r] - w[l - 1];
};

i64 get_b(int l, int r, vector<i64> &b) {
    if (l > r) return 0;
    if (l == 0) return b[r];
    return b[r] - b[l - 1];
};

i64 get(int l, int r, int tp, vector<i64> &w, vector<i64> &b) {
    if (tp == 1) {
        return r - get_w(l, r, w) + 1;
    }
    return l + get_b(l, r, b) - 1;
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    i64 n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s += s;
    vector<i64> w(2 * n + 10), b(n * 2 + 100);
    for (i64 i = 0; i < n; i++) {
        if (s[i] == '1') {
            w[i]++;
            w[i + n]++;
        } else {
            b[i]++;
            b[i + n]++;
        }
    }
    for (i64 i = 1; i <= 2 * n; i++) {
        w[i] += w[i - 1];
        b[i] += b[i - 1];
    }

    i64 t = w[n - 1];
    vector<vector<i64> > node(n + 1);
    vector<pair<i64, i64> > mp(n + 1);
    vector<i64> vis(n + 1);
    i64 tt = 0;
    for (i64 i = 0; i < n; i++) {
        if (vis[i]) continue;
        i64 tmp = i;
        while (!vis[tmp]) {
            vis[tmp] = 1;
            node[tt].emplace_back(tmp);
            mp[tmp] = {tt, node[tt].size()};
            tmp = (tmp + t) % n;
        }
        tt++;
    }
    debug(node);
    for (int i = 1; i <= m; i++) {
        int p_j, l_j, r_j;
        cin >> p_j >> l_j >> r_j;
        p_j--, l_j--, r_j--;
        if (l_j > r_j) r_j += n;
        if (l_j == r_j) {
            cout << dis1(p_j, l_j, n, mp, node) << endl;
        } else {
            i64 ans = -1;
            i64 p1 = get(l_j, r_j, 1, w, b);

            if (get_b(p1, r_j, b) == get_w(l_j, p1 - 1, w) && s[l_j] == '1') {
                i64 dd = dis1(p_j, p1, n, mp, node);
                if (dd != -1) {
                    ans = dd + r_j - l_j;
                }
            }
            int p2 = get(l_j, r_j, 0, w, b);
            if (get_b(p2 + 1, r_j, b) == get_w(l_j, p2, w) && s[r_j] == '0') {
                i64 dd = dis1(p_j, p2, n, mp, node);
                if (dd != -1) {
                    if (ans == -1) {
                        ans = dd + r_j - l_j;
                    } else {
                        ans = min(dd + r_j - l_j, ans);
                    }
                }
            }
            cout << ans << endl;
        }
    }
    //ac ac ac AC AC AC
}
```cpp

```cpp