正文
(全国多校重现赛一)A-Big Binary Tree
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
You are given a complete binary tree with n nodes. The root node is numbered 1, and node x's father node is ⌊x/2⌋⌊x/2⌋. At the beginning, node x has a value of exactly x. We define the value of a path as the sum of all nodes it passes(including two ends, or one if the path only has one node). Now there are two kinds of operations:
1. change u x Set node u's value as x(1≤u≤n;1≤x≤10^10)
2. query u Query the max value of all paths which passes node u.
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
题意：给你一个数N,代表一个二叉树的节点数，二叉树的每个节点的初始值为节点编号，即node[1]=1,node[2]=2....;然后有M个操作分别为：query k.查询经过节点k的一的一条链的最长长度；
题解：对于未修改之前，对于任意节点，其右儿子，必定大于其左儿子。因此，我们可以求出find_cnt(u)，返回u的子节点连成的权值最大的一条链，对于查询来说，只需求出num[u](节点u上的值)+find_cnt(u<<1)+find_cnt(u<<1|1) 最大值，不断更新最大值（沿着节点u往上更新一直到根节点），对于更新，只需判断新值与旧值得大小，。然后不断往上更新。
参考代码为：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,ll>dp,num;
int n,m;
char s1[10];
ll find(int u)
{
return num.count(u)?num[u]:u;
}
ll find_cnt(int u)
{
if(!u||u>n) return 0;
if(dp.count(u)) return dp[u];
int v,flag1=0,flag2=0;
for(v=u;v<=n;++flag1,v<<=1);
for(v=u;v<=n;++flag2,v=v<<1|1);
if(flag1!=flag2) v=n;
else v>>=1;
ll ans=0;
for(;v>=u;ans+=v,v>>=1);
return ans;
}
void update(int u,ll x)
{
num[u]=x;
while(u)
{
dp[u]=max(find_cnt(u<<1),find_cnt(u<<1|1))+find(u);
u>>=1;
}
}
ll query(int u)
{
ll ans=find(u)+find_cnt(u<<1)+find_cnt(u<<1|1);
ll tot=find_cnt(u);
while(u)
{
ans=max(ans,tot+find_cnt(u^1)+find(u>>1));
u>>=1; tot+=find(u);
}
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
dp.clear(); num.clear();
while(m--)
{
int u;ll x;
scanf("%s%d",s1,&u);
if(s1[0]=='q') printf("%lld\n",query(u));
else
{
scanf("%lld",&x);
update(u,x);
}
}
}
return 0;
}
