前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2017 Multi-University Training Contest - Team 9 1001&&HDU 6161 Big binary tree【树形dp+hash】

2017 Multi-University Training Contest - Team 9 1001&&HDU 6161 Big binary tree【树形dp+hash】

作者头像
Angel_Kitty
发布2018-04-09 15:52:16
4860
发布2018-04-09 15:52:16
举报
文章被收录于专栏:小樱的经验随笔

Big binary tree

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

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 ⌊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

代码语言:javascript
复制
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

代码语言:javascript
复制
17
17
17
16
17
17
12
12
12
11
12
12

Source

2017 Multi-University Training Contest - Team 9

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6161

分析:考虑dp,f(x)表示从点x开始向下走得到的最大的点权和,查询直接从x开始向上走更新答案即可。 考虑快速算 f(x) 对于子树内没有被修改过的点的 f(x) 可以快速分类讨论算出,而不满足本条件的点只有 O(mlogm) 个,在hash上dp即可。

下面给出AC代码:

代码语言:javascript
复制
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define pb push_back
 4 #define mkp make_pair
 5 #define fi first
 6 #define se second
 7 #define ll long long
 8 #define M 1000000007
 9 #define all(a) a.begin(), a.end()
10 
11 int n, m;
12 char s[20];
13 map<int, ll> mp;
14 map<int, int> amp;
15 
16 inline ll askmax(int u){
17     if(u > n) return 0;
18     if(mp.count(u)) return mp[u];
19     else{
20         int l = u, r = u;
21         while(l * 2 <= n){
22             l <<= 1;
23             r = (r << 1) | 1;
24         }
25         r = min(r, n);
26         ll res = 0;
27         while(r >= u) res += r, r >>= 1;
28         return res;
29     }
30 }
31 
32 inline int ask(int x){
33     return amp.count(x) ? amp[x] : x;
34 }
35 
36 int main(){
37     while(~scanf("%d%d", &n, &m)){
38         mp.clear();
39         amp.clear();
40         while(m--){
41             int x, v;
42             scanf("%s", s);
43             if(s[0] == 'c'){
44                 scanf("%d%d", &x, &v);
45                 amp[x] = v;
46                 for(; x; x >>= 1)
47                     mp[x] = max(askmax(x << 1), askmax((x << 1) | 1)) + ask(x);
48             }else{
49                 scanf("%d", &x);
50                 int px = x;
51                 ll res = 0, now = 0;
52                 for(; x >> 1;){
53                     bool k = ~x & 1; x >>= 1;
54                     now += ask(x);
55                     ll tmp = askmax(x << 1 | k);
56                     if(now + tmp > res) res = now + tmp;
57                 }
58                 res += askmax(px);
59                 res = max(res, askmax(px << 1) + askmax(px << 1 | 1) + ask(px));
60                 printf("%lld\n", res);
61             }
62         }
63     }
64     
65 #ifndef ONLINE_JUDGE
66     system("pause");
67 #endif
68     return 0;
69 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-09-02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Big binary tree
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档