Apple Tree(树状数组+dfs序)

Apple Tree

对问题的分析设计过程

这道题需要对一颗树的节点进行如下操作:

  • 单点修改
  • 对子树节点求和

考虑到没有其他操作可以考虑使用dfs序和树状数组实现

程序中用到的数据机构和算法

该程序使用dfs序和树状数组。将树做一次dfs遍历,并记录每个节点的访问顺序,可以发现节点的子树都对应访问顺序上的一个子区间。该题可变为对序列的单点修改和区间求和,即可用树状数组解决

程序的运行情况

提交了三次才通过,提交情况如下:

在实习过程中得到的经验和体会

  1. 在提交时一定记得要把Debug信息给删除
  2. 树状数组在处理一系列简单的数列操作和询问时是一种非常简便的,可以替代线段树的视线方案

代码

BZOJ 1062: [NOI2008]糖果雨(二维树状数组)

题目链接:

首先嘛,这道题是非同一般的恶心= =

然后首先膜拜一下CDQ大神ORZ在考场上A了这道题ORZ

这道题看到的话,我是先想把云朵化成在0s时的位置,但很容易发现这样只能单点查询而不能查询整段

结果只能膜拜题解了QAQ

首先先把云朵化成在第x秒到达0点长度为len(x是mod 2len意义下的)

每朵云就能变成一个点了

然后就可以发现询问其实是两个平行四边形内有多少个点

吧两个平行四边形化成矩形就行了

需要注意的是

一个平行四边形可能两个矩形

要么单独求

要么可以把图扩大一倍就行了= =

Code:

 

4105: [Thu Summer Camp 2015]平方运算

首先嘛这道题目只要知道一个东西就很容易了:所有循环的最小公约数<=60,成一条链的长度最大为11,那么我们就可以用一个很裸的方法。对于在链上的数,我们修改直接暴力找出并修改。对于在环上的数,我们对每一步建立一颗线段树,那么修改就变成了交换60棵线段树的某个子树。然后我们就可以愉快的写啦~~~

在想的时候被同学坑了,他说最长的循环不超过60.。。。

在实现方面,我用一个map+树状数组维护链上的答案,然后用60棵线段树来维护这个环。懂了之后还是很好写哒~~~

Code:

 

[Usaco2014 Open Gold ]Cow Optics (树状数组+扫描线/函数式线段树)

这道题一上手就知道怎么做了= =

直接求出原光路和从目标点出发的光路,求这些光路的交点就行了

然后用树状数组+扫描线或函数式线段树就能过了= =

大量的离散+模拟+二分什么的特别恶心,考试的时候是想到了不过被代码难度吓到了根本不想写QAQ

这时官方的代码就显现出了c++的STL的强大功能了

离散sort+unique+resize+lower_bound直接秒杀,模拟也是lower_bound+讨论直接秒杀

不得不让我这种一直还在手打二分的情何以堪啊QAQ

比较一下吧 官方3K,一同学(c++)6K,两初中的(Pascal)9K和20K (不得不感叹初中生已经突破天际了啊= =,不过那个20K的6个快排也是醉了= =)

CODE:(强烈建议学习其离散化的写法)

BZOJ 1103: [POI2007]大都市meg(dfs序,树状数组)

本来还想链剖的,结果才发现能直接树状数组的= =

记录遍历到达点与退出点的时间,然后一开始每个到达时间+1,退出时间-1,置为公路就-1,+1,询问直接点1到该点到达时间求和就行了- –