题目描述

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继续回答上面的问题。

Input

第一行有两个正整数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 m,n≤10000

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

题目分析

可修改的区间k大值= =
我们可以使用树状数组套主席树
利用树状数组的性质 每次查询或修改 拿出log棵主席树 对这些主席树做修改即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int read()
{
    int sum=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') sum=sum*10+(c-'0'),c=getchar();
    return sum;
}
struct your
{
    int lson,rson,size;
}a[10010*800];
int root[10100],tot;
void update(int x,int &y,int l,int r,int dx,int c)
{
    y=++tot;
    a[y].size=a[x].size+c;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(dx<=mid) a[y].rson=a[x].rson,update(a[x].lson,a[y].lson,l,mid,dx,c);
    else a[y].lson=a[x].lson,update(a[x].rson,a[y].rson,mid+1,r,dx,c);
}
char s[10];
int L[70],R[70];
int cntl,cntr;
int suml,sumr;
int val[10010];
int ask(int l,int r,int c)
{
    if(l==r) return l;
    suml=0,sumr=0;
    for(int i=1;i<=cntl;i++) suml+=a[a[L[i]].lson].size;
    for(int i=1;i<=cntr;i++) sumr+=a[a[R[i]].lson].size;
    int mid=(l+r)>>1;
    if(sumr-suml>=c)
    {
        for(int i=1;i<=cntl;i++) L[i]=a[L[i]].lson;
        for(int i=1;i<=cntr;i++) R[i]=a[R[i]].lson;
        return ask(l,mid,c);
    }
    else
    {
        for(int i=1;i<=cntl;i++) L[i]=a[L[i]].rson;
        for(int i=1;i<=cntr;i++) R[i]=a[R[i]].rson;
        return ask(mid+1,r,c-(sumr-suml));
    }
}
int find(int x,int y,int k)
{   
    cntl=cntr=0;
    for(int i=x-1;i;i-=i&-i) L[++cntl]=root[i];
    for(int i=y;i;i-=i&-i) R[++cntr]=root[i];
    return ask(1,1e9+10,k); 
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) val[i]=read(),val[i]++;
    for(int i=1;i<=n;i++) 
        for(int j=i;j<=n;j+=j&-j)
            update(root[j],root[j],1,1e9+10,val[i],1);
    for(int x,y,k,i=1;i<=m;i++)
    {
        scanf("%s",&s[0]);
        if(s[0]=='Q')
        {
            x=read(),y=read(),k=read();
            printf("%d\n",find(x,y,k)-1);
        }
        else
        {
            x=read(),k=read();
            for(int j=x;j<=n;j+=j&-j) 
                update(root[j],root[j],1,1e9+10,val[x],-1);
            val[x]=k+1;
            for(int j=x;j<=n;j+=j&-j) 
                update(root[j],root[j],1,1e9+10,val[x],1);
        }
    }
    return 0;
}