# hdu 6161-Big binary tree（思想-压缩空间）

www.MyException.Cn  网友分享于：2013-09-28  浏览：0次
hdu 6161--Big binary tree（思维--压缩空间）

Problem Description

You are given a complete binary tree with n nodes. The root node is numbered 1, and node x's father node is

Input
There are multiple cases.
For each case:
The first line contains two integers n,m(1≤n≤10^8,1≤m≤10^5), which represent the size of the tree and the number of operations, respectively.
Then m lines follows. Each line is an operation with syntax described above.

Output
For each query operation, output an integer in one line, indicating the max value of all paths which passes the specific node.

Sample Input
6 13
query 1
query 2
query 3
query 4
query 5
query 6
change 6 1
query 1
query 2
query 3
query 4
query 5
query 6

Sample Output
17
17
17
16
17
17
12
12
12
11
12
12

如求经过D的最大路径权值和。有以下的路径：1、起始为从D的叶子节点经D到D的另一个叶子节点。 2、从D的叶子节点经D B 到B的一个叶子节点。  3、从D的一个叶子节点经B D A 到A的一个叶子节点。所以求经过D的最大路径权值和时就是由D开始向上搜索D的祖先节点，进行计算。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
map<int,LL>mp;
map<int,LL>mx;
LL ans;
int n,m;
int pos[100];

void init()
{
int tmp=n;
int deep=(int)log2(n)+1;
for(int i=deep;i>=1;i--)
{
pos[i]=tmp;
tmp>>=1;
}
}

void cal(int x)
{
if(mp.count(x)) return ;
if(x>n) { mp[x]=0; return ; }
int deep=(int)log2(x)+1;
LL tmp=0;
for(int i=x;i<=n;i=(i<<1|1)) tmp+=i;
if(pos[deep]==x){
LL sum=0;
for(int i=deep;;i++)
{
sum+=pos[i];
if(pos[i]==n) break;
}
tmp=max(tmp,sum);
}
mp[x]=tmp;
}

void update(int x)
{
if(!x) return ;
LL y;
if(mx.count(x)==0) y=x;
else y=mx[x];
cal(x<<1);
cal(x<<1|1);
mp[x]=max(mp[x<<1],mp[x<<1|1])+y;
update(x>>1);
}

void query(LL sum,int x,int son)
{
if(!x) return ;
cal(x<<1);
cal(x<<1|1);
if(!mx.count(x)) mx[x]=x;
ans=max(ans,sum+mp[son^1]+mx[x]);
sum+=mx[x];
query(sum,x>>1,x);
}

int main()
{
char s[10];
while(scanf("%d",&n)!=EOF)
{
init();
mp.clear();
mx.clear();
scanf("%d",&m);
while(m--)
{
scanf("%s",s);
if(s[0]=='q')
{
int x; scanf("%d",&x);
cal(x<<1);
cal(x<<1|1);
if(!mx.count(x)) mx[x]=x;
ans=mp[x<<1]+mp[x<<1|1]+mx[x];
cal(x);
query(mp[x],x>>1,x);
printf("%lld\n",ans);
}
else
{
int x; LL y; scanf("%d%lld",&x,&y);
mx[x]=y;
update(x);
}
}
}
return 0;
}