F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Big binary tree

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1029    Accepted Submission(s): 385

Problem Description

You are given a complete binary tree with n nodes. The root node is numbered 1, and node x's father node is $\left \lfloor x/2 \right \rfloor$. 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


Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2023 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2023-06-01 00:27:37, Gzip enabled Administration