hdu6161 Big binary tree

多校1001
题目链接
题目是给一棵完全二叉树，从上到下从左到右给每个节点标号，每个点有权值，初始权值为其标号，然后有两种操作：
1、把u点权值改为x
2、查询所有经过u点的路径中，路径上的点权和最大。
节点有n个，修改有m个，n<=1e8 ,m<= 1e5
我们容易想到维护一个dp[u]代表从u点往下走能获得最大的权值

dp[u] = max(dp[u<<<1] , dp[u<<1|1]) + a[u] ;(a[u]为其本身的权值)

当我们修改某个点的权值时，只要更新其父节点到根节点的权值即可，
然后查询某个点时，由于所有节点都是正数，那么路径选的越长越好，所以在纸上画一下可以知道，这条路径可能是以该点为根的子树，从左子树的叶子走到右子树的叶子，也就是dp[u] = dp[u<<1|1] + dp[u<<1] + a[u] ；也有可能从这个点再往上走，然后走到某个点时往当前同父的另一个子节点走(用纸上画一下可以知道)
但是！！！最坑的是这个节点数非常大，会爆空间，但是我们发现如果一个点，其子树上的点都没被修改过，那么它的a[u],dp[u]都是可以通过初始值算出来的，也就是不需要开这部分空间，我们只关心询问中涉及到的点 。询问中会涉及到的点数最多<=1e5*(log n)*2，那么我们可以把这部分点放到map里，然后其他不涉及到的点都是可以直接算出来的 。

#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<time.h>
#include<cstdio>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<iostream>
#include<stdlib.h>
using namespace std;
#define  LONG long long
const LONG  INF=0x3f3f3f3f;
const LONG  MOD=1e9+7;
const double PI=acos(-1.0);
#define clrI(x) memset(x,-1,sizeof(x))
#define clr0(x) memset(x,0,sizeof x)
#define clr1(x) memset(x,INF,sizeof x)
#define clr2(x) memset(x,-INF,sizeof x)
#define EPS 1e-10
#define lson  l , mid , rt<< 1
#define rson  mid + 1 ,r , (rt<<1)|1
#define root 1, n , 1
LONG n , m ;
map<LONG ,LONG > dp ;
map<LONG ,LONG > a;
LONG Get_dp(LONG u)
{LONG tmp = u ;LONG res = 0 ;while(tmp <= n){res += tmp ;tmp = tmp*2 + 1;}LONG ret = 0 ;tmp = n ;int judge = 0 ;while(tmp){ret += tmp ;if(tmp == u){judge = 1;break ;}tmp /= 2;}if(judge )return max (ret ,res) ;else return res ;
}
int main()
{while(cin >> n >>m ){dp.clear () ;a.clear() ;char op[10] ;while(m -- ){scanf("%s",op) ;LONG  u ;if(op[0] =='q'){scanf("%lld",&u) ;LONG f1 ,f2 ,f3 ;if(dp[u<<1] == 0)f1 = Get_dp(u<<1 ) ;elsef1 = dp[u<<1] ;if(dp[u<<1|1] == 0)f2 = Get_dp(u<<1|1) ;else f2 = dp[u<<1|1] ;if(a[u] == 0)f3 = u ;else f3 = a[u] ;LONG ans = f1 + f2 + f3 ;LONG tmp = u ;LONG res ;if(dp[u] == 0) res = Get_dp(u) ;else res = dp[u] ;while(tmp>1ll){if(dp[tmp-1] == 0) f1 = Get_dp(tmp-1) ;else f1 = dp[tmp-1] ;if(dp[tmp+1] == 0) f2 = Get_dp(tmp+1) ;else f2 = dp[tmp+1] ;if(a[tmp/2] == 0) f3 = tmp/2 ;else f3 = a[tmp/2] ;if(tmp & 1ll)ans = max( ans , res + f1 + f3 ) ;elseans = max(ans , res + f2 + f3 ) ;res += f3 ;tmp /= 2 ;}printf("%lld\n",ans ) ;}else{LONG xx ;LONG tmp ;LONG ret = 0 ;scanf("%lld%lld",&u,&xx) ;ret = 0 ;if(dp[u] == 0)dp[u] = Get_dp(u) ;if(a[u] !=0) tmp = a[u] ;else tmp = u;dp[u] += ( xx - tmp ) ;a[u] = xx ;tmp = u/2;LONG f1,f2,f3 ;LONG temp ;while(tmp){if(a[tmp] !=0) f1 = a[tmp] ;else f1 = tmp ;if(dp[tmp<<1] != 0)f2 = dp[tmp<<1] ;elsef2 = Get_dp(tmp<<1) ;if(dp[tmp<<1|1] != 0) f3 = dp[tmp<<1|1] ;elsef3 = Get_dp(tmp<<1|1) ;dp[tmp] = f1 + max( f2 , f3 ) ;tmp/= 2;}}}a.clear() ;dp.clear() ;}
}