2 shunfurh shunfurh 于 2016.09.20 22:12 提问

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。

Input

对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

Output

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output

3
6

1个回答

caozhy
caozhy   Ds   Rxr 2016.09.20 22:22
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
[BZOJ1901][ZOJ2112]Dynamic Rankings-带修改的主席树-树状数组
Dynamic RankingsDescriptionThe Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbe
ZOJ 2112 Dynamic Rankings(主席树套树状数组+静态主席树)
题意:给定一个区间,求这个区间第k大的数,支持单点修改。 思路:主席树真是个神奇的东西.........速度很快但是也有一个问题就是占用内存的很大,一般来说支持单点修改的主席树套树状数组空间复杂度为O(n*logn*logn), 如果查询较少的话,可以初始的时候用一颗静态主席树,这样空间复杂度可以降为O(n*logn+q*logn*logn),勉强可以过zoj这道题。 这道题看了好久好久才懂.
【BZOJ1901】Dynamic Rankings,树状数组套主席树
裸题调了好久
Bzoj 1901 Zju2112 Dynamic Rankings(树状数组+主席树)
转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove 题目:给出一个序列,查询区间第K小,修改某个数 http://www.lydsy.com/JudgeOnline/problem.php?id=1901   对于每一个位置建立主席树,和静态主席树不一样。 由于 有修改操作,每一棵
ZOJ 2112 Dynamic Rankings (动态第k大,树状数组套主席树)★★
这题是动态第k大。   如果是不修改,直接主席树就可以了。 要修改要套如树状数组求和。 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const in
【bzoj1901】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,然后读入一系列的指令,包括询问指令和修改指令
树套树(线段树套平衡树)—— ZOJ 2112 Dynamic Rankings
对应题目链接:点击打开链接 Dynamic Rankings Time Limit: 10000MS   Memory Limit: 32768KB   64bit IO Format: %lld & %llu Submit Status Description The Company Dynamic Rankings ha
【bzoj1901】【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,然后读入一系列的指令,包括询问指令
【bzoj1901】Zju2112 Dynamic Rankings 线段树套平衡树
每个节点建一棵平衡树,结点个数为O(r-l+1),每一层结点个数为O(n),总结点个数为O(n log n) 对于Q操作: 二分答案,转化为区间[l,r]中小于等于ans的数有多少个,若>=k,则答案左移,否则答案右移 区间[l,r]对应线段树上O(log n)个节点,在每个节点的平衡树中进行查询,每次查询的复杂度是O(log n) 总复杂度O(log^3 n) 对于C操作: 对应修改
bzoj-1901 Dynamic Rankings
题意: 带修改区间k小值; n,m a[i] 题解: 听说是道裸题就过来刷刷 (卧槽我最近似乎都是在刷裸题); 写完前缀和的主席树感觉挺厉害,感受了一下树状数组就来写这题; 然后写更新的的时候我就不会了; 前缀和的时候,后一个树从前一个继承一部分结点而来的; 但是树状数组不能这么搞啊= =; 然后发现暴力建就可以了,也是犯二了; 最多n+m次修改,每次修改lo