转移自老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);
            }
        }
    }
}