• Apple Tree(树状数组+dfs序)

    Apple Tree(树状数组+dfs序)

    AppleTree对问题的分析设计过程这道题需要对一颗树的节点进行如下操作:单点修改对子树节点求和考虑到没有其他操作可以考虑使用dfs序和树状数组实现程序中用到的数据机构和算法该程序使用dfs序和树状数组。将树做一次dfs遍历,并记录每个节点的访问顺序,可以发现节点的子树都对应访问顺序上的一个子区间。该题可变为对序列的单点修改和区间求和,即可用树状数组解决程序的运行情况提交了三次才通过,提交情况如下:在实习过程中...

    02017年10月19日61树状数组
  • BZOJ 1062: [NOI2008]糖果雨(二维树状数组)

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

    题目链接:首先嘛,这道题是非同一般的恶心==然后首先膜拜一下CDQ大神ORZ在考场上A了这道题ORZ这道题看到的话,我是先想把云朵化成在0s时的位置,但很容易发现这样只能单点查询而不能查询整段结果只能膜拜题解了QAQ首先先把云朵化成在第x秒到达0点长度为len(x是mod2len意义下的)每朵云就能变成一个点了然后就可以发现询问其实是两个平行四边形内有多少个点吧两个平行四边形化成矩形就行了需要注意的是一个平行四边形...

    02017年4月3日119树状数组,老的存档
  • 4105: [Thu Summer Camp 2015]平方运算

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

    首先嘛这道题目只要知道一个东西就很容易了:所有循环的最小公约数<=60,成一条链的长度最大为11,那么我们就可以用一个很裸的方法。对于在链上的数,我们修改直接暴力找出并修改。对于在环上的数,我们对每一步建立一颗线段树,那么修改就变成了交换60棵线段树的某个子树。然后我们就可以愉快的写啦~~~在想的时候被同学坑了,他说最长的循环不超过60.。。。在实现方面,我用一个map+树状数组维护链上的答案,然后用60棵线段树来...

    02015年6月18日175树状数组,线段树,老的存档
  • [Usaco2014 Open Gold ]Cow Optics (树状数组+扫描线/函数式线段树)

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

    这道题一上手就知道怎么做了==直接求出原光路和从目标点出发的光路,求这些光路的交点就行了然后用树状数组+û...

    02014年12月16日189树状数组,老的存档
  • BZOJ 1103: [POI2007]大都市meg(dfs序,树状数组)

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

    本来还想链剖的,结果才发现能直接树状数组的==记录遍历到达点与退出点的时间,然后一开始每个到达时间+1,退出时间-1,置为公路就-1,+1,询问直接点1到该点到达时间求和就行了--[crayon-5a301be72bfe9090604520/] ...

    02014年11月18日266树状数组,老的存档