看着挺像线段树的,不是吗?但是不是,这是个STL中map的应用。

开始看数据,只有q个命令,u、v的数据也不算很大,有没有什么办法可以把命令存起来就好了。像python中字典那样,后来发现C++中的map,好东西啊。

说下思路,因为要计算u->v的权值之和,我们可以把权值放在v中,由于题目中给定的u、v特性,我们可以从最后一个v开始倒回来每次除以2,然后把权值加起来就好了,注意输入的区间大小值。


题目地址:http://codeforces.com/problemset/problem/696/A


Memory: 3800 KB
Time: 46 MS
Language: GNU G++ 5.1.0
Result: Accepted
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
#define LL long long
map<LL, LL>node;
int q, com;
LL u, v, w;
int main()
{
    while(~scanf("%d", &q)){
        while(q--){
            scanf("%d", &com);
            if(com==1){
                scanf("%lld%lld%lld", &u, &v, &w);
                while(u!=v){
                    if(u>v){
                        node[u]+=w;
                        u/=2;
                    }
                    else{
                        node[v]+=w;
                        v/=2;
                    }
                }
            }
            else{
                scanf("%lld%lld", &u, &v);
                LL ans=0;
                while(u!=v){
                    if(u>v){
                        ans+=node[u];
                        u/=2;
                    }
                    else{
                        ans+=node[v];
                        v/=2;
                    }
                }
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}