题意
题目是给一棵完全二叉树，从上到下从左到右给每个节点标号，每个点有权值，初始权值为其标号，然后有两种操作：
1、把u点权值改为x
2、查询所有经过u点的路径中，路径上的点权和最大。
节点有n个，修改有m个，n<=1e8 ,m<= 1e5
分析
注意到两个地方：1.完全二叉树 2.1e8个结点
这就说明，建图是不行的，一建就挂啊.怎么办呢？离散的思想，修改只有1e5个，其他结点的值又是标号本身，所以我们只需要用map映射存一下这被修改过的1e5个点就好了
这题怎么做呢？经过u点的路径中，点权和最大的，不就是u往下走最长的链+往上走最长的链吗或者u往左右两边走的路径之和？
那考虑维护每个点往下走最长的链。完全二叉树，只可能缺右边，不可能缺左边，尝试往左右两边下去最多能走多少层，如果走的层数一样，说明两条路都能到最下层，右结点的权值是2k+1>左结点2k，所以肯定一直沿着右边走。
然而如果走的层数不一样，说明从左边能到最后的节点，于是u能去的最下面的点就是n.
对于一个修改，只影响它的祖先结点的向下走最长的链，并不影响儿子，所以每次修改向上递归修改祖先。
而每次查询，分别查询自己往左右走的路径长度，再向上查询自己的祖先能走的长度。查的过程中比一下大小。
代码
#include<bits/stdc++.h> using namespace std; #define N 100010 #define ll long long #define lc (x<<1) #define rc (x<<1|1) #define fa (x>>1) map<int,ll>len,val; int n,m; char s[10]; ll cal(int x) { if(x>n)return 0; if(len.count(x))return len[x];//x向下走的路径长是否被算过，被算过就不用计算了 int t=x,dl=0,dr=0; //因为一个点的权值修改不会影响他儿子的向下走的路径长 ll ret=0; while(lc<=n)dl++,x=lc;//试探向左走的层数 x=t; while(rc<=n)dr++,x=rc;//试探向右走的层数 if(dl!=dr)x=n; while(x>=t)ret+=x,x=fa;//从最底端往上算 return ret; } inline void change(int x,int v) { val[x]=v; while(x) { len[x]=max(cal(lc),cal(rc))+(val.count(x)?val[x]:x); x=fa; } } inline ll query(int x) { ll d,ret; ret=cal(lc)+cal(rc)+(val.count(x)?val[x]:x);//计算x从两边向下走的路径长度 d=cal(x); while(fa) { int fg=x&1;//判断x是父亲节点的左儿子还是右儿子 x=fa; d+=(val.count(x)?val[x]:x);//每次把到了的节点的价值加进来 if(fg)ret=max(ret,d+cal(lc));//是左儿子，计算父亲的右边子树的答案 else ret=max(ret,d+cal(rc));//是右儿子，计算父亲的左边子树的答案 } return ret; } int main() { while(scanf("%d%d",&n,&m)==2) { len.clear();val.clear(); while(m--) { int x,y; scanf("%s",s); if(s[0]=='q') scanf("%d",&x),printf("%lld ",query(x)); else scanf("%d%d",&x,&y),change(x,y); } } }