[BZOJ1901/ZOJ2122/Luogu2617]Dynamic Rankings(树套树,树状数组,线段树)

发布于 2018-04-17  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1901/ZOJ2122/Luogu2617]Dynamic Rankings(树套树,树状数组,线段树)

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

Tag

树套树,树状数组,线段树

解决思路

如果是静态的化,就是主席树处理了。但由于有修改操作,如果用前缀和维护的话,查询是\(O(logn)\),但修改就是\(O(n)\)的了。
考虑一种更加均衡的前缀和的查询姿势。我们知道,树状数组的查询和修改都是\(O(logn)\)的,复杂度较均衡。那么可以用树状数组套值域线段树的方式来维护前缀和。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1901/ZOJ2122/Luogu2617]Dynamic Rankings(树套树,树状数组,线段树)


HNCJ OIer 一枚