P1247 -- RP堆

时间限制：1000MS

内存限制：131072KB

Description

众所周知，zgg天天DR，所以他总是无私地将体内的RP贡献给别人。

但是我们都想知道一个问题，就是为什么能飞使终能保持体内的RP平衡与超高的RP值呢。

原来，zgg体内的RP有一种特殊的存储方式，不同于我们一般人的随机分布，存取困难。

他体内有一个稳定的RP堆，他将各个RP分子从1到N编号，根节点的编号为1，如果某个RP分子X不是叶子节点，那么它的左儿子为RP分子2X,右儿子为RP分子2X+1。

这样一来，zgg每次DR时只需要将指定的两个RP分子结合就能以最小的RP损耗输出高额RP。注意zgg每次DR后体内RP会很快恢复平衡，以便保持下一次DR的状态。

注意DR时的RP损耗是那两个RP分子间的最短距离。

Input Format

输入第一行是一个整数N（2 <= N <= 100000000），表示RP分子个数。第二行有一个整数Q，一下Q行每行两个整数X,Y表示zgg将编号为X,Y的RP分子结合。

Output Format

输出包括Q行，每行只包含一个整数，就是DR时的RP损耗。

Sample Input

312 3

Sample Output

2

Hint

Data Limit

对于30%的数据，保证有Q <= 10000；

对于全部的数据，保证有Q <= 200000。

 

【题解】

其实这就是二叉树啊，树上节点求距离，水过。

数据有点大，0.95s，加输入优化卡过了时间。

1 #include
      
        2 using namespace std; 3 int read() { 4     int x=0; int f=1; 5     char ch=getchar(); 6     while(ch<'0'||ch>'9') {
    if(ch=='-') f=-1; ch=getchar();} 7     while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} 8     return x*f; 9 }10 int main() {11     int n=read(),q=read(),a,b,ans=0;12     for (int i=1;i<=q;i++,ans=0) {13         int x=read(),y=read();14         while(x!=y) {15             while(x>y) x>>=1,ans++;16             while(x
       
        >=1,ans++;17         }18         printf("%d\n",ans);19     }20     return 0;21 }