nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

hdu6161

题目大意 :
         给你一颗很大的完全二叉树，节点编号从1到n，对于除了1号节点以外的其他节点x，他的父亲是x>>1,1号节点为根，节点x的初始权值为x
给出两种操作：
1.update u x 意味着更新节点u的权值为x
2.query u 询问经过节点u的路径中，权值最大的条路径的权，（定义路径的权为路径上节点的权的和）
操作一共有m次
数据范围：n<1e8,m<1e5，x<1e10 时间：2s

        最开始考虑到这是一棵很大的树，我们不可能把这棵树建出来，太大了，空间肯定不够，注意到操作次数只有1e5，然后研究什么是最大路径的权？我们考虑任意一个节点u，他有三条边分别连向父亲fa，左儿子lson，右儿子rson，如果我们处理了以这三个点为起点且不经过u的路径的最值，那么我们就可以通过这三个数据转移过来。
        再考虑到这棵树是有规律的，节点数远大于操作数，那么我们依据各种高级数据结构中常用的懒惰标记（懒修改）来优化空间复杂度,来假装建立了这棵树，我们访问哪个节点，我们就为哪个节点开辟空间，其他的我们设置懒惰标记，表示此节点，以及他的整颗子树都被放置懒标记。
        处理完了空间以及询问操作，下一步是修改，当我们发现，我们修改了某个节点的值后，他以及他的祖先的向下的路径值都可能发生变化，这些节点的数量级是lg的，能够忍受，但是，这个节点的所有子孙向上的路径最值也有可能发生变化，这写节点的数量级是非常大的，远超线性。此时不能忽视，到此已经无解。
        看过题解以后，发现自己的解法离正解已经很接近了，首先第一点，正解说用map来储存树结构，这样子就不必去储存边，且大大优化了编码难度，然而却牺牲了时间，因为我们如果通过指针建树的话，从一个节点走向另一个节点可以O(1)办到，但是用map不行，map在这个基本操作上是O(lg)级别的，这就导致用map的话最终时间复杂度多一个lg。但是可以证明，多此lg，依旧可以过题，时间不会超。
        第二点，状态的选取：dp[x]代表以x为根的子树中以x为起点的路径的权的最大值。这个状态要好很多，相比我设的三个状态，第一他状态简单，第二单次修改的转移时间复杂度O(lgn)，因为他少一个向上的路径的状态，根本就不需要这个状态。
        修改权值的转移方程：
        从下至上，若修改节点x，且father为x的父亲，brother为x的兄弟，lson为x的左儿子，rson为x的右儿子，w代表点权，dp代表状态值，则dp[x]=max(dp[lson],dp[rson])+w[x]，
        dp[father]=max(dp[x],dp[brother])+w[father]。。。按此方法一直更新到根即可。
        询问路径的转移方程:
        依旧从下至上。肯定要去三个值的，x往左儿子的dp[x <<1]，x往右儿子的dp[x<<1|1]，然而，取不到父亲的值了，因为我们就没有维护这个状态值，不过还是有办法来得到它，我们考虑x往父亲的方向的最大路径值，这其实也可以递归下去，我们设这种值叫做up,利用动态规划，自顶向下搜索：x往父亲的权，在父亲那里只有两个方向可以走，因为是从x过来的，肯定不能回去的，那就少了一个方向，如果父亲继续向上走，我们可以递归下去，如果父亲向下走，那就只能走兄弟方向的路径，决策出现了：up[x]=w[x]+max(up[father],dp[brother])
        至此，更新和询问都已经解决，一个自底向上递归转移，一个自顶向下搜索转移。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct mydata{
    struct node{
        ll w,dp;
        node():w(0),dp(0){}
        node(ll w,ll dp):w(w),dp(dp){}
    };
    map<ll,node>tree;
    ll n;

    void ini(ll n){
        this->n=n;
        tree.clear();
    }

    inline node get(ll x){
        if(x>n)return node(0,0);

        node ret=tree[x];
        if(ret.w!=0)return ret;

        ll l=x,r=x;
        while(l<=n)l=l<<1;
        while(r<=n)r=r<<1|1;
        l>>=1;
        r>>=1;

        ll big=l<=r?r:n;
        ll dp=0;
        while(big>=x){
            dp+=big;
            big>>=1;
        }
        return tree[x]=node(x,dp);
    }

    void update(ll x,ll w){
        node l=get(x<<1);//lg
        node r=get(x<<1|1);//lg
        tree[x]=node(w,max(l.dp,r.dp)+w);//lg
        if(x==1)return;
        else update(x>>1,get(x>>1).w);
    }//lglg

    ll query(ll x){
        ll fa=max_sum_up(x);
        ll l=get(x<<1).dp;
        ll r=get(x<<1|1).dp;
        return fa+l+r-min(min(l,r),fa)+get(x).w;
    }

    ll max_sum_up(ll x){
        if(x==1)return 0;
        return get(x>>1).w+max(max_sum_up(x>>1),get(x^1).dp);
    }
}tree;

int main(){

    char str[10];
    ll n,m,u,x;
    while(~scanf("%lld%lld",&n,&m)){
        tree.ini(n);

        for(ll i=0;i<m;i++){
            scanf("%s",str);
            if(str[0]=='q'){
                scanf("%lld",&u);
                printf("%lld\n",tree.query(u));
            }
            else{
                scanf("%lld%lld",&u,&x);
                tree.update(u, x);
            }
        }
    }
}