首页 > 代码库 > 线段树总结

线段树总结

线段树总结

  参考NotOnlySuccess和shiqi_614的博客,做了线段树的专题。
单点更新:最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来
  1. hdu 1166 敌兵布阵 
  update:单点增减  query:区间求和 代码

  2. hdu 1754 I Hate It 
  update:单点替换  query:区间最值 代码

  3.hdu 1394 Minimum Inversion Number
  题意:求最小逆序数
  思路:用O(NlogN)的复杂度求出最初的逆序数,先建立一颗空树,然后插入一点x,计算[x,n)内有多少个值已经插入,然后将sum[x] = 1,并且向上pushup。
  update:单点增减 query:区间求和 代码

  4.hdu 2795 Billboard
  题意:有一个h * w 的板子,有n张纸条,为1 * wi。每次优先将纸条贴在板子左上角(不能重叠),输出贴在第几行。不能贴输出-1.
  思路:建一个有h个根节点的线段树(如果h>n,h =n),用mx[]数组来维护最值。
  query:区间求最值 代码

  5. poj 2828 Buy Tickets
  题意:有N个人排队,每一个人都有一个val来对应,每一个后来人都会插入当前队伍的某一个位置pos。要求把队伍最后的状态输出。
  思路:这道题最关键的是逆向处理,由于最后一个人的pos一定是最后的pos,然后将该位置从队列中去除,倒数第二个人也能够用同样的方式处理。先建立一颗树,树上的结点存sum值(表示该子树中没有人的位置个数)。每次插入一个人,将sum值更新。
  query:区间求和 代码

  6. poj 2886 Who Gets the Most Candies?
  题意:N 个小孩围成一圈,他们被顺时针编号为 1 到 N。每个小孩手中有一个卡片,上面有一个非 0 的数字,游戏从第 K 个小孩开始,他告诉其他小孩他卡片上的数字并离开这个圈,他卡片上的数字 A 表明了下一个离开的小孩,如果 A 是大于 0 的,则下个离开的是左手边第 A 个,如果是小于 0 的,则是右手边的第 -A 个小孩。游戏将直到所有小孩都离开,在游戏中,第 p 个离开的小孩将得到 F(p) 个糖果,F(p) 是 p 的约数的个数,问谁将得到最多的糖果。输出最幸运的小孩的名字和他可以得到的糖果。
  思路:这里用到了一个新的知识点。反素数 有了这个知识点就能知道p为多少时得到最多糖果,然后用线段树模拟约瑟夫环即可。要处理向左和向右数的细节,具体看代码。代码

  7. hdu4288 Coder
  题意:有三种类型的操作,(1)."add x",表示往集合里添加数x。(2).“del x”表示将集合中数x删除。(3).“sum”求出从小到大排列的集合中下标模5为3的数的和。集合中的数都是唯一的。解题报告
  
  8. CodeforcesBeta Round #19 D. Points 
  有三种操作“add x y”往平面上添加(x,y)这个点,"remove x y",将平面上已经存在的点(x,y)删除,“find x y”找出平面上坐标严格大于(x,y)的点,如果有多个点找x最小的,再找y最小的。解题报告

  9. poj2481 Cows
  有N头牛,每只牛有一个值[S,E],如果对于牛i和牛j来说,它们的值满足下面的条件则证明牛i比牛j强壮:Si <=Sjand Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值,要求输出每头牛有几头牛比其强壮。解题报告
  
(持续更新中)