int parent[MAX_N], size[MAX_N];

int get_root(int node){
	if(node == parent[node])
		return node;
	return get_root(parent[node]);
}
void union_sets(int u, int v){
	u = get_root(u);
	v = get_root(v);
	if(u == v)
		return;
	if(size[u] > size[v])
		swap(u, v);
	size[v] += size[u];
	parent[u] = v; 
}

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5+5;
int n, m, q, parent[MAX_N], time_changed[MAX_N], size[MAX_N];
int get_root(int node, int time){
	if(parent[node] == node || time_changed[node] > time)
		return node;
	return get_root(parent[node], time);
}
void union_sets(int a, int b, int time){
	a = get_root(a, time);
	b = get_root(b, time);
	if(a == b)
		return;
	if(size[a] > size[b])
		swap(a, b);
	size[b] += size[a];
	parent[a] = b;
	time_changed[a] = time;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++){
		parent[i] = i;
		size[i] = 1;
	}
	for(int i = 1; i <= m; i++){
		int a, b; cin >> a >> b;
		union_sets(a, b, i);
	}
	while (q--) {
		int a, b; cin >> a >> b;
		int l = 0, r = m, mid, ans = -1;
		while (l <= r) {
			mid = (l + r) / 2;
			if (get_root(a, mid) == get_root(b, mid)) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5+5;
int n, q, parent[MAX_N], time_changed[MAX_N];
vector<int>version[MAX_N], size[MAX_N];
int get_root(int node, int time){
	if(parent[node] == node || time_changed[node] > time)
		return node;
	return get_root(parent[node], time);
}
void union_sets(int a, int b, int time){
	a = get_root(a, time);
	b = get_root(b, time);
	if(a == b)
		return;
	if(size[a] > size[b])
		swap(a, b);
	parent[a] = b;
	time_changed[a] = time;
	version[b].push_back(time);
	size[b].push_back(size[a].back() + size[b].back());
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		parent[i] = i;
		version[i].push_back(0);
		size[i].push_back(1);
	}
	for(int i=1; i <= q;i++){
		int type; cin >> type;
		if(type == 1){
			int a, b; cin >> a >> b;
			union_sets(a, b, i);
		}else if(type == 2){
			int a, b, X; cin >> a >> b >> X;
			cout << (get_root(a, X) == get_root(b, X)? "YES" : "NO") << "\n";
		}else{
			int a, X; cin >> a >> X;
			a = get_root(a, X);
			int pos = upper_bound(version[a].begin(),version[a].end(),X) - version[a].begin();
			cout << size[a][pos-1] << "\n";
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5+5;
struct Node{
	int l = -1, r = -1, sz = -1, par = -1;
};
vector<Node>t;
void build(int i, int l, int r){
	if(l == r){
		t[i].par = l;
		t[i].sz = 1;
		return;
	}
	int mid = (l + r) / 2;
	t[i].l = t.size();
	t.emplace_back();
	build(t[i].l, l, mid);
	t[i].r = t.size();
	t.emplace_back();
	build(t[i].r, mid+1, r);
}
int nw(int j){
	int i = t.size();
	t.emplace_back();
	t[i].l = t[j].l;
	t[i].r = t[j].r;
	t[i].par = t[j].par;
	t[i].sz = t[j].sz;
	return i;
}
void upd(int i, int l, int r, int p, int v1, int v2){
	if(l == r){
		if(v1 != -1)t[i].par = v1;
		if(v2 != -1)t[i].sz = v2;
		return;
	}
	int mid = (l+r)/2;
	if(p <= mid){
		t[i].l = nw(t[i].l);
		upd(t[i].l, l, mid, p, v1, v2);
	}else{
		t[i].r = nw(t[i].r);
		upd(t[i].r, mid+1, r, p, v1, v2);
	}
}
int get_sz(int i, int l, int r, int p){
	if(l == r)return t[i].sz;
	int mid = (l + r) / 2;
	if(p <= mid)return get_sz(t[i].l, l,mid, p);
	return get_sz(t[i].r, mid+1, r, p);
}
int get_par(int i, int l, int r, int p){
	if(l == r)return t[i].par;
	int mid = (l + r) / 2;
	if(p <= mid)return get_par(t[i].l, l,mid, p);
	return get_par(t[i].r, mid+1, r, p);
}
int n, m, q, root[MAX_N];
int compress(int i, int j){
	int nxt = get_par(i, 1, n, j);
	if(nxt == j)return j;
	int root = compress(i, nxt);
	upd(i, 1, n, j, root, -1);
	return root;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	t.emplace_back();
	build(0, 1, n);
	while(q--){
		int type; cin >> type;
		if(type==1){
			int k, a, b; cin >> k >> a >> b;
			k--;
			m++;
			root[m]=nw(root[k]);
			compress(root[k], a);
			compress(root[k], b);
			a = get_par(root[k], 1, n, a);
			b = get_par(root[k], 1, n, b);
			if(a == b)continue;
			int szl = get_sz(root[k] ,1 ,n ,a), szr = get_sz(root[k], 1, n, b);
			if(szl > szr)swap(a, b);
			upd(root[m], 1, n, b, -1, szl+szr);
			upd(root[m], 1, n, a, b, -1);
		}else if(type==2){
			int k ,a ,b; cin >> k >> a >> b;
			k--;
			compress(root[k], a);
			compress(root[k], b);
			cout << (get_par(root[k], 1, n, a) == get_par(root[k], 1, n, b)? "YES" : "NO") << "\n";
		}else{
			int k, a; cin >> k >> a;
			k--;
			compress(root[k], a);
			cout << (get_sz(root[k], 1, n, get_par(root[k], 1, n, a))) << "\n";
		}
	}
	return 0;
}

The equation can be rearranged to be $$$2^K \le r-l+1$$$ (let $$$X = 2^K$$$ ). Then $$$K$$$ is at most $$$log_2(r-l+1)$$$

Notice you need the node to go to a lower depth and to the right (so its a left child), which means if the value of the parent is $$$M$$$ then the left child is $$$2 \cdot M$$$. So it needs to satisfy $$$M \bmod 2 \equiv 0$$$, generally we can know how the maximum number of times we can go up to the right in a row by finding the first ON bit (The Least Significant Bit). The answer using bits is $$$log_2(M \& -M)$$$. (Considering $$$M$$$ is the value of the node in the segment tree)

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    freopen("input.txt","w",stdout);
    mt19937 mt1(time(NULL));
    const int N = (1<<23),MX=1e9;
    cout<<N<<" "<<N<<"\n";
    for(int i=1;i<=N;i++){
        cout<<(mt1()%(MX+1))<<" ";
    }
    cout<<"\n";
    for(int i=1;i<=N;i++){
        int q = mt1()&1;
        cout<<q+1<<" ";
        if(q==0){
            cout<<(mt1()%N)<<" "<<(mt1()%(MX+1))<<"\n";
        }else{
            int l = mt1()%N;
            int r = (mt1()%(N+1-l))+l+1;
            cout<<l<<" "<<r<<"\n";
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = (1<<23);
long long seg[N<<2];
int x,q;
void upd(int l,int r){
	seg[l+=N-1]=r;
	while((l>>=1)>=1)seg[l]=seg[l<<1]+seg[l<<1|1];
}
long long qry(int l,int r){
	long long ret=0,k=0;l+=N-2,r+=N-1;
	while((l+=(1<<k))<=r)
		ret+=seg[l>>(k=min(__lg(l&-l),__lg(r-l+1)))];
	return ret;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	freopen("input.txt","r",stdin);
	ofstream time("time.txt");
	ofstream out("output.txt");
	auto st = chrono::steady_clock::now().time_since_epoch().count();
	cin>>x>>q;
	for(int i=0;i<x;i++)cin>>seg[N+i];
	for(int i=N-1;i>=1;i--)seg[i]=seg[i<<1]+seg[i<<1|1];
	for(int i=1;i<=q;i++){
		int t,l,r;cin>>t>>l>>r;
		if(t==1)upd(l+1,r);
		else if(t==2)out << qry(l,r) << "\n";
	}
	auto en = chrono::steady_clock::now().time_since_epoch().count();
	time << (en - st) / 1e9 << 's';
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = (1<<23);
long long seg[N<<2];
int x,q;
void upd(int l,int r){
	seg[l+=N-1]=r;
	while((l>>=1)>=1)seg[l]=seg[l<<1]+seg[l<<1|1];
}
long long qry(int l, int r) {
	long long res = 0;
	for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
		if (l&1) res += seg[l++];
		if (r&1) res += seg[--r];
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	freopen("input.txt","r",stdin);
	ofstream time("time.txt");
	ofstream out("output.txt");
	auto st = chrono::steady_clock::now().time_since_epoch().count();
	cin>>x>>q;
	for(int i=0;i<x;i++)cin>>seg[N+i];
	for(int i=N-1;i>=1;i--)seg[i]=seg[i<<1]+seg[i<<1|1];
	for(int i=1;i<=q;i++){
		int t,l,r;cin>>t>>l>>r;
		if(t==1)upd(l+1,r);
		else if(t==2)out << qry(l+1,r) << "\n";
	}
	auto en = chrono::steady_clock::now().time_since_epoch().count();
	time << (en - st) / 1e9 << 's';
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = (1<<23);
long long seg[N<<2];
int x,q;
void upd(int i,int l,int r,int s,int val){
	if(l==r){
		seg[i]=val;
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)upd(i<<1,l,mid,s,val);
	else upd(i<<1|1,mid+1,r,s,val);
	seg[i]=seg[i<<1]+seg[i<<1|1];
}
long long qry(int i,int l,int r,int s,int e){
	if(l>=s&&r<=e)return seg[i];
	int mid=(l+r)>>1;
	long long ret=0;
	if(s<=mid)ret+=qry(i<<1,l,mid,s,e);
	if(e>=mid+1)ret+=qry(i<<1|1,mid+1,r,s,e);
	return ret;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	freopen("input.txt","r",stdin);
	ofstream time("time.txt");
	ofstream out("output.txt");
	auto st = chrono::steady_clock::now().time_since_epoch().count();
	cin>>x>>q;
	for(int i=0;i<x;i++)cin>>seg[N+i];
	for(int i=N-1;i>=1;i--)seg[i]=seg[i<<1]+seg[i<<1|1];
	for(int i=1;i<=q;i++){
		int t,l,r;cin>>t>>l>>r;
		if(t==1)upd(1,1,N,l+1,r);
		else if(t==2)out << qry(1,1,N,l+1,r) << "\n";
	}
	auto en = chrono::steady_clock::now().time_since_epoch().count();
	time << (en - st) / 1e9 << 's';
	return 0;
}