https://atcoder.jp/contests/abc282/tasks/abc282_f
ST 表板子？？？
这怎么出的？
发现要每一个区间都能拆分成至多两个区间，那很明显就能联想到 ST 表的查询。
大概算一下发现区间个数 \(=\sum_{i=1}^{2^i\le n} n-i+1\le 43917<50000\)，明显可以用。
所以就仿照 ST 表的预处理和查询就行啦。
# include <bits/stdc++.h>
using namespace std;
const int N = 4000, M = 11;
int l2 [N + 10];
int k2 [M + 10];// k2 [i] 处理当前块长为 2^i 的起点方便得出答案
int main () {
for (int i = 3; i <= N; i ++) {
l2 [i] = l2 [(i + 1) >> 1] + 1;
}
int n;
cin >> n;
int m = 0;
for (int i = 1; i <= n; i <<= 1) {
m += n - i + 1;
}
cout << m << '\n';
cout << flush;
for (int i = 0; (1 << i) <= n; i ++) {
if (i) {
k2 [i] = k2 [i - 1] + n - (1 << (i - 1)) + 1;
}
for (int j = 1; j + (1 << i) - 1 <= n; j ++) {
cout << j << ' ' << j + (1 << i) - 1 << '\n';
cout << flush;
}
}// 预处理
int q;
cin >> q;
while (q --) {
int x, y;
cin >> x >> y;
int L = l2 [y - x + 1];
cout << k2 [L] + x << ' ' << k2 [L] + y - (1 << L) + 1 << '\n';// 查询
cout << flush;
}
return 0;
}