EularTour.cpp

#include <bits/stdc++.h>
using namespace std;
struct Treap {
    int val, pr, sz;
    Treap *l,*r;
    Treap(int v):val(v),pr(rand()),sz(1),l(nullptr),r(nullptr){}
};
int sz(Treap* t){ return t? t->sz : 0; }
void upd(Treap* t){ if(t) t->sz = 1 + sz(t->l) + sz(t->r); }
Treap* merge(Treap* a, Treap* b){
    if(!a) return b; if(!b) return a;
    if(a->pr < b->pr){ a->r = merge(a->r,b); upd(a); return a; }
    else { b->l = merge(a,b->l); upd(b); return b; }
}
void split(Treap* t, int k, Treap*& a, Treap*& b){ // split by size
    if(!t){ a=b=nullptr; return; }
    if(sz(t->l) < k){ split(t->r, k - sz(t->l) -1, t->r, b); a=t; upd(a); }
    else { split(t->l, k, a, t->l); b=t; upd(b); }
}
// Full Euler Tour Tree implementation requires mapping nodes to occurrences and more helpers.
// Due to complexity, this is a template showing treap primitives.
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<"Treap primitives provided for Euler Tour Tree. Complete link/cut using occurrences mapping.\n";
    return 0;
}