题目大意 :
给你一颗很大的完全二叉树，节点编号从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);
}
}
}
}