Dynamic LCA

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <deque>
#include <iomanip>
#include <fstream>
#include <ctime>
#include <random>
#include <queue>
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define sz(a) (int)((a).size())
#define fixed cout << setprecision(15) << fixed;
#define all(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define debug2(x, y) cerr << #x << " = " << x <<", "<< #y << " = " << y <<"\n";
#define debug3(x, y, z) cerr << #x << " = " << x << ", "<< #y << " = " << y << ", "<< #z << " = " << z <<"\n";
#define debug_a(x) cerr << #x << '\n'; for (auto e : (x)) cerr << e << ' '; cout << '\n';
#define debug_b(x) cerr << #x << '\n'; for (auto e : (x)) cerr << " ( " << e.first.first << ' ' << e.first.second << " ) "; cout << '\n';
#define pikachu push_back
#define st first
#define nd second
#pragma GCC optimize("Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
const ll N = 5e4 + 2, INF = 1e9;
/// /////////////////////////////////////////////////////////////////
struct vertex {
    ll num, deep, add, cnt, prior;
    pair<ll, ll> min;
    vertex* r, * l, * parent;
    ll type;
};
/// ////////////////////////////////////////////////////////
vector<vertex*> ver(N);
ll boss[N], rang[N];
ll get_boss(ll a) {                             // DSU
    if (boss[a] == a) return a;
    boss[a] = get_boss(boss[a]);
    return boss[a];
}
void dsu(ll a, ll b) {
    ll x = get_boss(a);
    ll y = get_boss(b);
    if (rang[x] > rang[y]) swap(x, y);
    boss[x] = y;
    rang[y] += rang[x];
}
//////////////////////////////////////////////////////////////
ll cnt(vertex* v) { if (v == NULL) return 0; return v->cnt; }
pair<ll, ll> min2(vertex* v) { if (v == NULL) return { INF, -1 }; return v->min; }
/// //////////////////////////////////////////////////////////////////////////
void upd(vertex * v) {                             // Обновление cnt, min + родителей
    if (v == NULL) return;
    if (v->l != NULL) v->l->parent = v, v->l->type = 0;
    if (v->r != NULL) v->r->parent = v, v->r->type = 1;
    v->min = min(min(min2(v->l), min2(v->r)), { v->deep, v->num });
    v->cnt = 1 + cnt(v->r) + cnt(v->l);
}
void push(vertex * v) {
    if (v == NULL) return;
    v->deep += v->add;
    v->min.st += v->add;
    if (v->l != NULL) v->l->add += v->add;
    if (v->r != NULL) v->r->add += v->add;
    v->add = 0;
}
/// /////////////////////////////////////////////////////////////////////////////////////
ll pos(vertex* v) {                         // Взятие порядквого номера вершины
    if (v == NULL) return 0;
    ll ans = pos(v->parent);
    if (v->type == 0) ans -= cnt(v->r) + 1;
    else ans += cnt(v->l) + 1;
    return ans;
}
vertex* lead(vertex* v) {                 // Взятие главной вершины дерева
    if (v->parent == NULL) return v;
    return lead(v->parent);
}
/// /////////////////////////////////////////////////////////////////////
vertex* merge(vertex * l, vertex * r) {
    push(l);
    push(r);
    if (l == NULL or r == NULL) {
        if (l == NULL) return r;
        else return l;
    }
    if (l->prior > r->prior) {
        l->r = merge(l->r, r);
        push(l->l);
        upd(l);
        return l;
    }
    else {
        r->l = merge(l, r->l);
        push(r->r);
        upd(r);
        return r;
    }
}
pair<vertex*, vertex*> split(vertex * T, ll key, ll add = 0) {
    if (T == NULL) {
        return { NULL, NULL };
    }
    push(T);
    ll z = add + cnt(T->l);
    if (z < key) {
        auto t = split(T->r, key, z + 1);
        T->r = t.st;
        push(T->l);
        upd(T);
        return { T, t.nd };
    }
    else {
        auto t = split(T->l, key, add);
        T->l = t.nd;
        push(T->r);
        upd(T);
        return { t.st, T };
    }
}
/// /////////////////////////////////////////////////////////////////////////////
void unite(ll a, ll b) {
    if (get_boss(a) == get_boss(b) || ver[b]->deep != 0) return;
    auto T = lead(ver[a]);
    auto T2 = lead(ver[b]);
    ll ps = pos(ver[a]);
    auto t = split(T, ps);
    auto d = split(t.st, ps - 1);
    T2->add += d.nd->deep + 1;
    vertex* v = new vertex{ ver[a]->num, d.nd->deep, 0, 1, rand(), {d.nd->deep, ver[a]->num}, NULL, NULL, NULL, 1 };
    T = merge(merge(d.st, d.nd), T2);
    T = merge(T, v);
    T = merge(T, t.nd);
    dsu(a, b);
}
/// //////////////////////////////////////////////////////////////////
ll lca(ll a, ll b) {
    if (get_boss(a) != get_boss(b)) return 0;
    auto T = lead(ver[a]);
    ll p1 = pos(ver[a]);
    ll p2 = pos(ver[b]);
    if (p1 > p2) swap(p1, p2);
    auto t = split(T, p2);
    auto d = split(t.st, p1 - 1);
    ll ans = d.nd->min.nd;
    T = merge(merge(d.st, d.nd), t.nd);
    return ans;
}
/// ////////////////////////////////////////////////////////////////////////
ll n, m, x, y, t, ans = 0;
int main() {
    ios;
    for (ll i = 0; i < N; i++) rang[i] = 1, boss[i] = i;
    for (ll i = 0; i < N; i++) {
        ver[i] = new vertex{ i, 0, 0, 1, rand(), {0, i}, NULL, NULL, NULL, 1 };
    }
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> x;
        if (x != 0) unite(x, i);
    }
    cin >> m;
    for (ll i = 0; i < m; i++) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y;
            ll u = ((x + ans - 1) % n) + 1;
            ll v = ((y + ans - 1) % n) + 1;
            unite(v, u);
        }
        else {
            cin >> x >> y;
            ll u = ((x + ans - 1) % n) + 1;
            ll v = ((y + ans - 1) % n) + 1;
            ans = lca(u, v);
            cout << ans << '\n';
        }
    }
}