机器人

题目大意

现在机器人有一种移动方式，问机器人从某一个起点到达 $l_i$ $r_i$ 位置。

题解思路

思考一 $n$个点, $n$ 条边的图是什么图 ？很明显这是一个基环树。这样我们在求解距离的时候似乎可以转换为环上的两点之间的距离，这样通过一系列离线的操作，可以在 O(n)的时间下求出来。

思考二 现在我们从 $p_0$ 出发， 走到 $l_i, r_i$,这会有什么性质，

• 首先出去最后一次移动到的位置，其他的位置都产生了相应的影响。这样我们可以找到开始位置 $p_1$
• 还有没有其他性质？设最后一步是向右走，那么 $l_i$ 位置一定是白色的。最后一步是向左走 $r_i$ 的位置一定是黑色。
• $l_i \sim p_1$ 这个位置每一个向右的位置相当于一次转向。在$p_i \sim r_i$ 的位置也是类似。那这个有什么性质呢？我们定$p_i$有一个初始方向 $a_0$ ,结束的方向为 $a_1$ ,如果两个方向相反，那么可以说明左区间的右转向和右区间的左转向数目相同。如果两个方向相同，最终向右走，那么左区间的右转向比右区间的左转向多一个，向左走也类似。

参考代码

 
 #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;
        }
    }
    //
}