codeforces 696A Lorenzo Von Matterhorn 水题

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int N  = 3e6;
const LL mod = 1e9+7;
map<LL,LL>mp;
int get(LL x){
  for(int i=0;;++i){
    LL tmp1=(1ll<<i);
    LL tmp2=(1ll<<(i+1))-1;
    if(x>=tmp1&&x<=tmp2)return i;
  }
}
int main(){
  int q;
  scanf("%d",&q);
  while(q--){
    LL u,v,w;
    int op;
    scanf("%d%I64d%I64d",&op,&u,&v);
    int curu=get(u),curv=get(v);
    if(curu<curv){swap(u,v);swap(curu,curv);}
    if(op==1){
      scanf("%I64d",&w);
      while(curu>curv){
        if(mp.find(u)==mp.end())mp[u]=w;
        else mp[u]+=w;
        u>>=1;--curu;
      }
      while(u!=v){
        if(mp.find(u)==mp.end())mp[u]=w;
        else mp[u]+=w;
        if(mp.find(v)==mp.end())mp[v]=w;
        else mp[v]+=w;
        u>>=1;v>>=1;
      }
    }
    else{
       w=0;
       while(curu>curv){
        if(mp.find(u)!=mp.end())w+=mp[u];
        --curu;u>>=1;
       }
       while(u!=v){
        if(mp.find(u)!=mp.end())w+=mp[u];
        if(mp.find(v)!=mp.end())w+=mp[v];
        u>>=1;v>>=1;
       }
       printf("%I64d\n",w);  
    }
  }
  return 0;
}