\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法 0: Sparse table
長さ \(2^{i}\) の区間を用意して，それらの組み合わせで 区間を覆うことができる． 区間を指定されたとき，sarse table から使う幅 \(w\) を全探索する． \([l, l+w) \cup [r-w, r) = [l,r)\) となる \(w\) を見つける． \(w\) を小さい方から探していき，初めて覆っているもので break.
解法 1: 分割統治法
分割統治なら，disjoint union で区間を書くことが出来る． 区間を真ん中で割って，右端が左右どちらに入るかを考えて， より小さい区間に帰着する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
map<pll,ll> mp;
{
vector<pll> p;
for(ll w = 1; w <= n; w<<=1){
for(ll l = 0; l+w <= n; l++){
ll r = l+w;
mp[{l,r}] = mp.size();
p.emplace_back(l,r);
}
}
cout << p.size() << endl;
for(auto [l,r]: p){
cout << l+1 << " " << r << endl;
}
}
auto get = [&](ll l, ll r) -> ll {
return mp[{l,r}] + 1;
};
{
ll q; cin >> q;
rep(qi,q){
ll l,r; cin >> l >> r;
--l;
ll w = 1;
while(2*w < r-l) w <<= 1;
cout << get(l,l+w) << " " << get(r-w,r) << endl;
}
}
return 0;
}
