预处理，RMQ求区间最大值。
代码如下：
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 typedef long long LL;10 const int N = 4444444;11 const int M = 22;12 int pre[N], RMQ[M][N >> 2];13 int dfs(LL n) {14 if (n <= 0) cout << n << endl;15 if (n < N && pre[n]) return pre[n];16 int tmp;17 if (n & 1) tmp = dfs(n * 3 + 1) + 1;18 else tmp = dfs(n >> 1) + 1;19 if (n < N) pre[n] = tmp;20 return tmp;21 }22 23 void PRE() {24 pre[1] = 1;25 for (int i = 2, end = N >> 2; i < end; i++) if (pre[i] == 0) dfs(i);26 // for (int i = 1; i < 20; i++) cout << i << ' ' << pre[i] << endl;27 // prepare RMQ28 for (int i = 0, end = N >> 2; i < end; i++) RMQ[0][i] = pre[i];29 for (int i = 1; i < M; i++) {30 for (int j = 0, end = (N >> 2) - (1 << i); j <= end; j++) {31 RMQ[i][j] = max(RMQ[i - 1][j], RMQ[i - 1][j + (1 << i - 1)]);32 }33 }34 }35 36 int query(int l, int r) {37 if (l > r) swap(l, r);38 int ep = (int) log2((double) r - l + 1);39 return max(RMQ[ep][l], RMQ[ep][r - (1 << ep) + 1]);40 }41 42 int main() {43 PRE();44 int l, r;45 while (cin >> l >> r) cout << l << ' ' << r << ' ' << query(l, r) << endl;46 return 0;47 }
——written by Lyon