codeforces基礎問題——#362(div 2)C

#362(Div 2) C

    ：           ，    1    ，    i        i * 2， i * 2 + 1， 
     q（1 <= q <= 1000）   :
    1.    u v            w；
    2.    u v        ；

1 <= u, v <= 1018, w <= 109

  
        C      ，      ，          ，      map，      LCA           。

#include 
#include 
using namespace std;
typedef long long LL;
int log(LL x)
{
    int l = 0;
    while(x) x >>= 1, l ++;
    return l;
}
mapm;
int main()
{
    int q, ty, c;
    LL a, b;
    scanf("%d", &q);
    for (int i = 1; i <= q; i ++) {
        scanf("%d %I64d %I64d", &ty, &a, &b);
        if (ty == 1) scanf("%d", &c);
        int l1 = log(a), l2 = log(b);
        LL sum = 0;
        while(l1 > l2){ 
            if (ty == 1) m[a] += c;
            else sum += m[a];
            a = a / 2, l1 --;
        }
        while(l1 < l2){
            if (ty == 1) m[b] += c;
            else sum += m[b]; 
            b = b / 2, l2 --;
        }
        while(a != b){
            if (ty == 1) m[a] += c, m[b] += c;
            else sum += m[a] + m[b]; 
            a = a / 2, b = b / 2;
        }
        if (ty == 2) printf("%I64d
", sum);
    }

    return 0;
}