Codeforces Round #362 (Div. 2) C. Lorenzo Von Matterhorn LCA(最近公共祖先)

ProLightsfx 2016-8-23 132 8/23
C. Lorenzo Von Matterhorn LCA(最近公共祖先)

Source

Codeforces Round #362 (Div. 2)

 

My Solution

LCA(最近公共祖先) 在有根树中,找出某两个结点u和v最近的公共祖先(或者说,离树根最远的公共祖先)。

类似于这样来访问

inline int LCA(const int &u, const int &v)
{
while (u != v){
if(u < v){ //if(v < u){
swap(u, v);
}
u = u/2;        // v/2 is parent of vertex v
}
return u;
}

每次修改的时候直接修改就行

1e18  -> 2^63次所以每次 2*63*q == 1e5

复杂度 O(2*63*n)

 

此外对于 map<pair<LL, LL>, LL> mpt;//map tree

和 map<LL, map<LL, LL> > mpt;//map tree

前面用 Codeforces上的数据做了测试, 这两种写法时间上是差不多的, 然而在空间复杂度上 前者是后者的一半

Codeforces Round #362 (Div. 2) C. Lorenzo Von Matterhorn     LCA(最近公共祖先)

所以以后就用map<pair<LL, LL>, LL> mpt;//map tree 来处理 1<= u, v <= 1e18, w 这样节点标号很大的情况好了

如果时间压的比较紧可能可以尝试用
FF 计算机...  柱爷

离散化

vector<pair<int,int>> G[N]

读完后sort每个G[i]

后面二分找

 

#include 
#include 
#include 



#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

map<pair<LL, LL>, LL> mpt;//map tree

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false);
    cin.tie(0);

    LL q, op, u, v, w, ans;
    cin>>q;
    while(q--){
        cin>>op>>u>>v;
        if(op == 1){
            cin>>w;
            while(u != v){
                if(u < v){
                    swap(u, v);
                }
                mpt[make_pair(u / 2, u)] += w;
                u /= 2;
            }
        }
        else{
            ans = 0;
            while(u != v){
                if(u < v){
                    swap(u, v);
                }
                ans += mpt[make_pair(u / 2, u)];
                u /= 2;
            }
            cout<<ans<<endl;
        }
    }

    #ifdef LOCAL
    printf("n");
    }
    #endif // LOCAL
    return 0;
}

 

 

 

非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx

- THE END -

ProLightsfx

11月15日21:03

最后修改:2024年11月15日
0

非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

共有 0 条评论