就是简单模拟，加记忆化，加线段树加速查询。
恩，注意输入中i和j不保证i<=j，就是这个让我WA2次。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-5-13
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#define MAXN 1000000
int f[MAXN+2];
int st[MAXN<<2];
int max(int a,int b)
{
return a>b?a:b;
}
void build_segment_tree(int L=1,int R=MAXN,int root=1)
{
if (L==R) st[root]=f[L];
else
{
int LL=L,LR=(L+R)>>1,Lroot=root<<1;
int RL=LR+1,RR=R,Rroot=Lroot|1;
build_segment_tree(LL,LR,Lroot);
build_segment_tree(RL,RR,Rroot);
st[root]=max(st[Lroot],st[Rroot]);
}
}
int get_max(int l,int r,int L=1,int R=MAXN,int root=1)
{
if (r<L||l>R) return 0;
if (l<=L&&R<=r) return st[root];
else
{
int LL=L,LR=(L+R)>>1,Lroot=root<<1;
int RL=LR+1,RR=R,Rroot=Lroot|1;
return max(get_max(l,r,LL,LR,Lroot),
get_max(l,r,RL,RR,Rroot));
}
}
int main()
{
f[1]=1;
for (int i=2;i<=MAXN;i++)
{
long long int n=i;
int step=0;
for (;;)
{
if (n<=MAXN&&f[n])
{
step+=f[n];
break;
}
step++;
if (n&1) n=((n<<1)|1)+n;
else n>>=1;
}
f[i]=step;
}
build_segment_tree();
int i,j;
while (scanf(“%d%d”,&i,&j)!=EOF)
if (i<=j) printf(“%d %d %d\n”,i,j,get_max(i,j));
else printf(“%d %d %d\n”,i,j,get_max(j,i));
return 0;
}