专栏首页小樱的经验随笔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】

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

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

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代码:

 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 回溯算法入门及经典案例剖析(初学者必备宝典)

    前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

    Angel_Kitty
  • “玲珑杯”ACM比赛 Round #12题解&源码

    我能说我比较傻么!就只能做一道签到题,没办法,我就先写下A题的题解&源码吧,把官方给出的题解贴出来! A -- Niro plays Galaxy Note ...

    Angel_Kitty
  • POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

    Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

    Angel_Kitty
  • Tree - 687. Longest Univalue Path

    Given a binary tree, find the length of the longest path where each node in the ...

    用户5705150
  • 原 初学图论-DAG单源最短路径算法

    不高不富不帅的陈政_
  • 在VS2010上使用C#调用非托管C++生成的DLL文件(图文讲解) 背景

    背景      在项目过程中,有时候你需要调用非C#编写的DLL文件,尤其在使用一些第三方通讯组件的时候,通过C#来开发应用软件时,就需要利用DllImpor...

    庞小明
  • 仿qq最新侧滑菜单

    为了后续对这个项目进行优化,比如透明度动画、背景图的位移动画,以及性能上的优化。 我把这个项目上传到github上面,请大家随时关注。 github地址 htt...

    xiangzhihong
  • Tree - 298. Binary Tree Longest Consecutive Sequence

    298 . Binary Tree Longest Consecutive Sequence

    用户5705150
  • 用 WPF 写的颜色拾取器

    之前都是用别人的颜色拾取器,今天自己用WPF写了一个颜色拾取器小程序 拾取鼠标所在位置的颜色,按键盘上的空格键停止取色 程序下载:MyWPFScreenColo...

    lpxxn
  • BZOJ2152: 聪聪可可(点分治)

    聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况...

    attack

扫码关注云+社区

领取腾讯云代金券