题目大意：给定一棵完全二叉树$(n \leqslant 10^8)$ ，每个点点权默认为层序遍历顺序标号。有$m$ 次操作：
- 把$u$ 点的点权改为$x$ 。
- 查询所有经过$u$ 的路径中，点权和最大的路径。
DP
设$a[p]$ 为结点$p$ 的点权。
可以维护一个数组$dp[p]$ 表示从结点$p$ 向下的所有路径中最大的点权和。
转移方程：$dp[p]=max(dp[p<<1],dp[p<<1|1])+a[p]$ 。
因为每个点的点权均为正数，故经过点$p$ 的点权和最大的路径只能为从该点左子树走到右子树的路径或者从该点出发向上走到某个祖先转向另一个孩子。
前者的值为$dp[p<<1]+dp[p<<1|1]+a[p]$ ，$O(1)$ 复杂度。
后者可以暴力求解，因为是完全二叉树，故复杂度为$O(logn)$ 。
修改的时候仅当前结点及其祖先受到影响，暴力修改，同理复杂度为$O(logn)$ 。
因为$n$ 是$10^8$ 级别的，故没有修改过的结点直接$O(logn)$ 求出，用unordered_map修改过的值。
总复杂度$O(mlogn)$ 。
代码如下：
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int N=1000005;
unordered_map<ll,ll>dp(N),a(N);
ll n,m,p,x;
char op[7];
void init(){
dp.clear();
a.clear();
}
ll get_value(ll p){
ll u=0,v=0,tmp=p;
while(tmp<=n){
u+=tmp;
tmp=tmp<<1|1;
}
tmp=n;
while(tmp>p){
v+=tmp;
tmp>>=1;
}
if(tmp==p)return max(u,v+p);
return u;
}
ll query(ll p){
ll l=dp[p<<1],r=dp[p<<1|1],v=a[p];
if(!l&&(p<<1)<=n)l=get_value(p<<1);
if(!r&&(p<<1|1)<=n)r=get_value(p<<1|1);
if(!v)v=p;
ll ans=l+r+v,tmp=dp[p];
if(!tmp)tmp=get_value(p);
while(p!=1){
ll rt=a[p>>1],son=dp[p/2*4+1-p];
if(!rt)rt=p>>1;
if(!son&&(p/2*4+1-p)<=n)son=get_value(p/2*4+1-p);
tmp+=rt;
ans=max(ans,tmp+son);
p>>=1;
}
return ans;
}
void push_up(ll p){
ll l=dp[p<<1],r=dp[p<<1|1],v=a[p];
if(!l&&(p<<1)<=n)l=get_value(p<<1);
if(!r&&(p<<1|1)<=n)r=get_value(p<<1|1);
if(!v)v=p;
dp[p]=max(l,r)+v;
}
void updata(ll p,ll x){
ll l=dp[p<<1],r=dp[p<<1|1];
if(!l&&(p<<1)<=n)l=get_value(p<<1);
if(!r&&(p<<1|1)<=n)r=get_value(p<<1|1);
dp[p]=max(l,r)+x;
a[p]=x;
while(p!=1){
push_up(p>>1);
p>>=1;
}
}
int main(void){
while(~scanf("%I64d%I64d",&n,&m)){
init();
while(m--){
getchar();
scanf("%s",op);
if(op[0]=='q'){
scanf("%I64d",&p);
printf("%I64d\n",query(p));
}else if(op[0]=='c'){
scanf("%I64d%I64d",&p,&x);
updata(p,x);
}
}
}
}