The 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 numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.
Your task is to write a program for this computer, which
- Reads N numbers from the input (1 <= N <= 50,000)
- Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.
Input
The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.
The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format
Q i j k or
C i t
It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.
There're NO breakline between two continuous test cases.
<b< dd="">
Output
For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])
There're NO breakline between two continuous test cases.
<b< dd="">
Sample Input
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
题解：
树状数组的每个节点都是一颗线段树，但这棵线段树不再保存每个前缀的信息了，而是由树状数组的sum函数计算出这个前缀的信息，那么显而易见这棵线段树保存的是辅助数组S的值，即S=A[i-lowbit+1]+...+A[i],其中A[i]表示值为i的元素出现的次数。
那么对于每次修改，我们要修改树状数组上的logn棵树，对于每棵树，我们要修改logn个结点，所以时空复杂度为
O(（n+q）*logn*logn)，由于这道题n比较大，查询次数q比较小，所以我们可以初始时建立一颗静态的主席树，树状数组只保存每次修改的信息，那么时空复杂度降为了O（n*logn+q*logn*logn）
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
typedef long long ll;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
}
const int maxn=6e4+;
struct Tree{
int ls,rs;
int sum;
} node[maxn*]; struct Qnode{
bool flag;
int l,r,k;
} qn[maxn]; int T,n,q,a[maxn],b[maxn],num,rt[maxn];
char str[];
int ul[maxn],ur[maxn],ca[maxn],s[maxn],cnt; void Build(int rt,int l,int r)
{
rt=++cnt;
node[rt].sum=;
if(l==r) return ;
int mid=l+r>>;
Build(node[rt].ls,l,mid);
Build(node[rt].rs,mid+,r);
} void Update(int y,int &x,int l,int r,int pos,int val)
{
node[++cnt]=node[y];node[cnt].sum+=val;x=cnt;
if(l==r) return ;
int mid=l+r>>;
if(pos<=mid) Update(node[y].ls,node[x].ls,l,mid,pos,val);
else Update(node[y].rs,node[x].rs,mid+,r,pos,val);
} void Add(int x,int val)
{
int res=lower_bound(b+,b++num,a[x])-b;
while(x<=n)
{
Update(s[x],s[x],,num,res,val);
x+=lowbit(x);
}
} int Sum(int x,bool temp)
{
int res=;
while(x>)
{
if(temp) res+=node[node[ur[x]].ls].sum;
else res+=node[node[ul[x]].ls].sum;
x-=lowbit(x);
}
return res;
} int Query(int L,int R,int x,int y,int l,int r,int k)
{
if(l==r) return l;
int mid=l+r>>;
int res=Sum(R,true)-Sum(L,false)+node[node[y].ls].sum-node[node[x].ls].sum;
if(k<=res)
{
for(int i=R;i;i-=lowbit(i)) ur[i]=node[ur[i]].ls;
for(int i=L;i;i-=lowbit(i)) ul[i]=node[ul[i]].ls;
return Query(L,R,node[x].ls,node[y].ls,l,mid,k);
}
else
{
for(int i=R;i;i-=lowbit(i)) ur[i]=node[ur[i]].rs;
for(int i=L;i;i-=lowbit(i)) ul[i]=node[ul[i]].rs;
return Query(L,R,node[x].rs,node[y].rs,mid+,r,k-res);
}
} int main()
{
T=read();
while(T--)
{
n=read();q=read(); cnt=num=;
memset(rt,,sizeof(rt));
for(int i=;i<=n;++i) a[i]=read(),b[++num]=a[i];
for(int i=;i<=q;++i)
{
scanf("%s",str);
if(str[]=='Q')
{
qn[i].flag=true;
qn[i].l=read();qn[i].r=read();qn[i].k=read();
}
else
{
qn[i].flag=false;
qn[i].l=read();qn[i].r=read();b[++num]=qn[i].r;
}
}
sort(b+,b++num);
int tot=unique(b+,b++num)-b-;
num=tot;
for(int i=;i<=n;++i) ca[i]=lower_bound(b+,b++num,a[i])-b;
Build(rt[],,num);
for(int i=;i<=n;++i) Update(rt[i-],rt[i],,num,ca[i],);
for(int i=;i<=n;++i) s[i]=rt[];
for(int i=;i<=q;++i)
{
if(qn[i].flag)
{
for(int j=qn[i].r;j;j-=lowbit(j)) ur[j]=s[j];
for(int j=qn[i].l-;j;j-=lowbit(j)) ul[j]=s[j];
printf("%d\n",b[Query(qn[i].l-,qn[i].r,rt[qn[i].l-],rt[qn[i].r],,num,qn[i].k)]);
}
else
{
Add(qn[i].l,-);
a[qn[i].l]=qn[i].r;
Add(qn[i].l,);
}
}
} return ;
}