Hi guys, I've been introduced to dynamic connectivity for a long time, especially dsu rollback which can be operated in O(log n) for updating and asking the root. Now, I'm facing with a problem with the edges stricting to only attach i and i + 1 and since the time limit is tight, I may have to do in O(1) (I'd tried the above one but it didn't work).

I was introduced to using left right for this at the same time, however it comes to a problem that the range that I get when updating some edges nearby isn't just what I've expected.

For example, I have 5 nodes here:

If I use edge (3, 4), (4, 5), (1, 2) and (2, 3) accordingly then there exists a position u which left[u] != 1 or left[u] != 5.

Please let me know where I implement wrong or prove that it's impossible to optimize it into O(1) for both updating and getting the longest range that u is covered.

    vector <int> lef_m(n), rig_m(n);
    vector <pair <int, int>> rollback;
    auto Rollback = [&] {
        while (not rollback.empty()) {
            int u, v; tie(u, v) = rollback.back();

            rig_m[u] = u; lef_m[v] = v;

            rollback.pop_back();
        }  
    };
    auto Join = [&] (int u, int v, int temp) {
        if (rig_m[u] >= v) return;
        
        if (temp) rollback.emplace_back(u, v);

        rig_m[u] = rig_m[v];
        lef_m[v] = lef_m[u];
    };