hdu 离线处理题目集锦

预处理，打表，全部读入询问一起处理，适当运用这些技巧可以大大降低时间复杂度。

hdu 3874   hdu 3333

题意：n个数，m个询问，求[l,r] 区间和，其中相同的数只计算一次。

case<=10; n<=50 000; m<=200 000; a[i] <=1000 000

离线处理：把m个询问按照 r 递增的顺序排序。用right[]，记录每个数最后一次出现的位置。每次处理到 q[i]. r ，将最新出现的位置赋值为该数，前一次出现的位置清零，（用树状数组维护）并更新right[] 数组。  然后计算sum(r) - sum(l-1) 即可。

思路分析：查询数量过多，离线可降低时间复杂度。 通过前缀和计算结果，所以通常以R增序排序。由于是R增序，所以当前区间的R大于等于之前的，因此把重复出现的数字置为0不会影响结果。

hdu 4638

题意：给定一个1~n的排列，问区间[l,r]之间有多少段连续的数。比如区间里有3,1,2,5,6 这五个数，那么就有3,1,2和5,6这两端。

分析：跟上题很相似，把连续的数当做同一个数，只记录该段中最后出现的数。

离线处理：按照R升序排列。pod[ x]记录 x 出现的位置。处理到位置 i 时，先add( i , 1)，然后看 val [i]-1，val [i] +1所在的位置，如果位置在 i 的前方，就 add(pos[ val[i]-1 ],-1)，add(pos[ val[i]+1 ],-1)。 答案就是：sum(query[i].r)-sum(query[i].l-1)

hdu 2874

题意：给定n个节点，m条边的森林，再给定q个查询，求每次查询森林里两个点的最近距离。

n，m<=10 000， q《=1000 000；

解题思路：离线LCA， 然后求a,b两点间的最短距离=dis[a] +dis[b]-2*dis[c]，c为a,b的最近公共祖先

hdu 4630

题意：有n个数，是1~n的一个排列。有m个询问，每次询问一个区间，问从这个区间中，任取两个数a,b，gcd(a,b)的最大值。

解题思路：区间内gcd(a,b)的最大值：出现两次以上的因子的最大值。

离线处理：首先预处理出1~n每个数的因子，并存起来；

将所有询问按照R从小到大排序。

用last[i]记录因子i上次出现的位置。

然后对每个数的因子i，将上次出现该因子的位置上更新为i。（用线段树维护区间最大值）

hdu 3726（待研究）(10天津区域赛G)

题意：n个顶点，m条边，每个顶点有给定的权值。q次操作：

D X：删除第x条边

Q x k：查询节点x所在联通块的所有顶点中第K大点权（ps：all vertexes currently connected with vertex X，注意理解）

C x v：将点x的权值修改为v

输出所有查询的均值

解题思路：离线算法

对于删除，可以通过将所有操作读入后，从后往前处理。把删除边转换成插入边。

　　 对于查询第k大顶点，我们可以使用 treap维护的名次树 kth来实现

对于修改操作，我们先将原来的值删除，然后再插入新值。 因为我们使用离线逆向处理，则修改操作也会逆向。

hdu 4288（12成都网赛）（待研究）

题意：维护一个有序数列{An}，有三种操作：1、添加一个元素。2、删除一个元素。3、求数列中下标%5 = 3的值的和。

解题思路：线段树中不支持添加、删除操作，所以用离线做法。

由于添加删除会影响区间内对应的有效值%5的值，所以线段树要维护5个值，sum[ 0 ~4 ]。

hdu 4417(12杭州网赛)

题意：给你n个数，m个查询，对于一个查询问在[l,r]范围内小于h的数有多少个。

n<=100 000, m<=100 000。h<=1000 000 000;

树状数组的离线处理：将输入的n个数从小到大排序，也将查询按他们查询的数从小到大排序。从小到大到这n个数放进树状数组里，当小于一个查询的c的所有的数都在放进数状数组里面的时候，查询[a,b]范围内有多少个数。

归来赛 kAri-OJ 399 都谁有趣（为hdu 4777热身）

题意：给定序列，查询区间内，前有比自己小的数，后有比自己大的数的数字的个数。

离线思路：预处理出每个数距离自己最近的“前小”，“后大”。（维护一个单调栈）转化为统计前驱和后继都在区间内的数字的个数。

用vector[ x ]记录以x为后继的数字的前驱。便于处理时统一操作。

将查询以R升序排列，对后继为x <=q[i].r 的点的前驱做标记（树状数组该位置加1）。对于每个询问，sum(r)-sum(l-1)即为答案。

hdu 4777 （13杭州站H）

题意：n个数，m个询问，求[l,r]有多少个数与其他数均互质。

n,m,a[i]<=200 000

分析：可转化为统计区间内与其他数不互质的数的个数，即最近的不互质的数在区间内。

答案=区间长度- 前驱在区间内-后继在区间内+前驱后继都在区间内

即：=区间长度- 后继在区间内- 前驱在区间内但后继不在区间内

离线思路：预处理出每个数距离自己最近的不互质的数的位置。（用质数去扫，降低时间复杂度）

将查询以R升序排列。处理小于等于R的位置，现将该位置数的前继加上标记。然后扫描以该点为后继的位置，取消对位置前继的标记，并标记该位置。（解释：被标记的点分两部分，后继在区间内的点，后继不在区间内的点的前继）。

统计时，( r-l+1 )- ( sum(r) - sum(l-1) ) 即为答案。（解释：答案里的点分两部分，后继在区间内且该点在区间内的点，后继不在区间内且前继在区间内的点）

最后

以上就是直率彩虹为你收集整理的hdu 离线处理题目集锦的全部内容，希望文章能够帮你解决hdu 离线处理题目集锦所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。