257. 动态排名系统
时间限制：5 s 内存限制：512 MB
[问题描述]
给定一个长度为N的已知序列A[i](1<=i<=N)，要求维护这个序列，能够支持以下两种操作：
1、查询A[i],A[i+1],A[i+2],...,A[j](1<=i<=j<=N)中，升序排列后排名第k的数。
2、修改A[i]的值为j。
所谓排名第k，指一些数按照升序排列后，第k位的数。例如序列{6,1,9,6,6}，排名第3的数是6，排名第5的数是9。
[输入格式]
第一行包含一个整数D(0<=D<=4)，表示测试数据的数目。接下来有D组测试数据，每组测试数据中，首先是两个整数N(1<=N<=50000),M(1<=M<=10000)，表示序列的长度为N，有M个操作。接下来的N个不大于1,000,000,000正整数，第i个表示序列A[i]的初始值。然后的M行，每行为一个操作
Q i j k 或者
C i j
分别表示查询A[i],A[i+1],A[i+2],...,A[j](1<=i<=j<=N)中，升序排列后排名第k的数，和修改A[i]的值为j。
[输出格式]
对于每个查询，输出一行整数，为查询的结果。测试数据之间不应有空行。
[样例输入]
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
[样例输出]
3
6
3
6
题解：
（如果你没有听过“树状数组套主席树”这个概念，你选择可以移步我的讲解http://www.cnblogs.com/LadyLex/p/7275164.html）
本题就是一个树状数组套主席树的板子题，如果用指针打的话操作时可以用vector存下需要更改的几棵树，进行修改
查询时候和普通的静态查询也是类似的，只不过是子树数据数量之和与k比较
这些东西还是通过代码可以更好的理解……代码见下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=,MAXN=1000000000ll;
int n,val[N],tp;
struct node
{
node *ch[];int cnt;
node(){cnt=;ch[]=ch[]=NULL;}
inline void update(){cnt=ch[]->cnt+ch[]->cnt;}
}*null=new node(),*root[N*];
vector<node*>v[];
inline node* newnode()
{
node *o=new node();
o->ch[]=o->ch[]=null;
return o;
}
inline int lowbit(int a){return a&-a;}
inline void get_query(int id,int pos)
{
v[id].clear();
while(pos)v[id].push_back(root[pos]),pos-=lowbit(pos);
}
inline void get_set(int id,int pos)
{
v[id].clear();
while(pos<=n)v[id].push_back(root[pos]),pos+=lowbit(pos);
}
inline void set(vector<node*> o,int l,int r,int pos,int opt)
{
while(l<r)
{
int mi=(l+r)>>;
for(int i=,len=o.size();i<len;i++)if(o[i]!=null)o[i]->cnt+=opt;
if(pos<=mi)
{
r=mi;
for(int i=,len=o.size();i<len;o[i]=o[i]->ch[],i++)
if(o[i]->ch[]==null)o[i]->ch[]=newnode();
}
else
{
l=mi+;
for(int i=,len=o.size();i<len;o[i]=o[i]->ch[],i++)
if(o[i]->ch[]==null)o[i]->ch[]=newnode();
}
}
for(int i=,len=o.size();i<len;i++)
{
if(o[i]==null)o[i]=newnode();
o[i]->cnt+=opt;
}
}
inline int query(int a,int b,int l,int r,int k)
{
get_query(,a-);get_query(,b);
while(l<r)
{
int tmp=,mi=(l+r)>>;
for(int i=,len=v[].size();i<len;i++)if(v[][i]!=null)tmp-=v[][i]->ch[]->cnt;
for(int i=,len=v[].size();i<len;i++)if(v[][i]!=null)tmp+=v[][i]->ch[]->cnt;
if(tmp>=k)
{
for(int i=,len=v[].size();i<len;i++)v[][i]=v[][i]->ch[];
for(int i=,len=v[].size();i<len;i++)v[][i]=v[][i]->ch[];
r=mi;
}
else
{
for(int i=,len=v[].size();i<len;i++)v[][i]=v[][i]->ch[];
for(int i=,len=v[].size();i<len;i++)v[][i]=v[][i]->ch[];
k-=tmp,l=mi+;
}
}
return r;
}
inline void change(int a,int b)
{get_set(,a);set(v[],,MAXN,val[a],-);set(v[],,MAXN,b,);val[a]=b;}
int main()
{
int m,a,b,c;char s[];
null->ch[]=null->ch[]=null;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)root[i]=newnode();
for(int i=;i<=n;i++)scanf("%d",&val[i]),get_set(,i),set(v[],,MAXN,val[i],);
while(m--)
{
scanf("%s",s);
if(s[]=='Q')scanf("%d%d%d",&a,&b,&c),printf("%d\n",query(a,b,,MAXN,c));
else scanf("%d%d",&a,&b),change(a,b);
}
}