喂你脚下有坑 3年前 树状数组 树状数组 本期我们来讲一讲树状数组，一个支持单点修改、区间求和的数据结构。（经过精巧的修改后，也可以支持区间修改&查询、单点修改&区间最大值） 假设我们有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，我们有两个操作： 修改操作：选择序列中的一个数字 a_k，给它增 […] 算法竞赛 1.36k 2 5
喂你脚下有坑 7年前 GCD ST表 倍增 树状数组 HDU 5869 Different GCD Subarray Query 传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5869 题目翻译 给一个序列，求[L,R]区间内，有多少个不同的子区间的区间GCD 题解 首先计算不同的GCD，我们使用离线询问，然后用树状数组/线段树把不同数记录在最后一次出现位置的方法。 然后如何计算不 […] 算法竞赛 517 0 0
喂你脚下有坑 7年前 Codeforces 主席树 异或 树状数组 离线 Codeforces #364 D. Mishka and Interesting sum 传送门：http://www.codeforces.com/contest/703/problem/D 题目翻译 一个长度为N的序列，m个询问，问[l,r]区间内出现偶数次的数字的Xor和。 题解 我们可以离线所有询问（不离线可以用主席树一样的方法搞，然而这里N=1e6空间开不下） 我们首先对序列做 […] 算法竞赛 629 0 0
喂你脚下有坑 7年前 容斥原理 数学 树状数组 2016多校训练Contest5：1012 World is Exploding 传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5792 题目翻译 有一个序列 An , 求四元组的数量 ( a , b , c , d ) ，满足 a≠b≠c≠d , 1≤a<b≤n , 1≤c<d≤n , Aa<Ab , Ac> […] 算法竞赛 574 0 0
喂你脚下有坑 8年前 OI 树套树 树状数组 线段树 BZOJ 2141: 排队 Description 排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为 […] 算法竞赛 638 0 0
喂你脚下有坑 8年前 OI 二分法 哈希 树套树 树状数组 树链剖分 线段树 BZOJ 1146: [CTSC2008]网络管理Network Description M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后 […] 算法竞赛 686 2 0
喂你脚下有坑 8年前 OI 平衡树 树套树 树状数组 BZOJ 3262: 陌上花开 Description 有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要 […] 算法竞赛 631 0 0
喂你脚下有坑 8年前 CDQ分治 OI 树状数组 BZOJ 3262: 陌上花开 Description 有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要 […] 算法竞赛 567 0 0
