Responsive image

问题 1880 --Big binary tree

1880: Big binary tree

时间限制: 4 Sec  内存限制: 128 MB
提交: 5  解决: 0
[提交][状态][讨论版][命题人:]

题目描述


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⌋. 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.
 

输入描述

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.
 

输出描述

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

样例输入

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

样例输出

17
17
17
16
17
17
12
12
12
11
12
12

来源

 

[提交][状态]
ACM算法攻关部