树状数组最原始的作用就是求前缀和,可以实现单点修改和区间查询。 但是假设现在有: 1.区间修改,单点查询 2.区间修改,区间查询 但是又不想敲线段树怎么办? 就用树状数组喽。 假设现在有一个原数组a(假设a[0] = 0),...
阅读(23) 评论(0)
题意: 有若干棵树,每棵树有横坐标xi和高度hi。 把若干棵树按照x递增排序,每棵树的rank是ri,那么定义两颗树的F为abs(ri-rj)。 把若干棵树按照高度递增排序,每棵树的rank是ri,定义两棵树的D为min(ri,r...
阅读(23) 评论(0)
题意: 有n * k块木板,每个木桶由k木板组成,每个木桶的容量定义为它最短的那块木板的长度。 任意两个木桶的容量v1,v2,满足|v1-v2| <= d。 问n个木桶容量的最大的和为多少,或者说明不可能做出这样的n个木桶。...
阅读(33) 评论(0)
题意: 给出一个数组,删除大于等于k的数字,使得其满足以下条件: 1.剩余的连续的段,每一段的长度相等; 2.在满足第一个条件的情况下,段数尽可能多; 3.在满足前两个条件的情况下,k取最小的。 求k。 思路: 一开始整个...
阅读(19) 评论(0)
题意: 定义一个函数f(a): 给出一个数组a,有q个询问,每次询问回答在l到r的区间内,连续子串的f函数的最大值。 思路: 画图,来自codeforces SheepRanger 由此图可知,f(l,r)...
阅读(27) 评论(0)