值域分块

分块求第k小（支持单点修改）

经过实测，大概只能过50000的样子。

分成sqrt（n）块， 块的大小为sqrt（n），块内维护有序数列。 修改就暴力重构块，显然不会超时

对于每一个询问，先二分一个区间权值（发现这道题是1~1e9），然后去统计所求的区间内小于这个数的个数有多少。对于两边不完整的块暴力统计，对于完整的块，则二分查找最小的~~数，即可在log时间内得到答案。

#include<bits/stdc++.h>
using namespace std;
int getint()
{
    int summ=0,f=1;
    char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }
    for(;isdigit(ch);ch=getchar())
        summ=(summ<<3)+(summ<<1)+ch-48;
    return summ*f;
}
#define int long long
int l[500],r[500],block,n,m,num,belong[100005],b[100005],a[100005],pos[100005];
void build()//预处理
{
    if(n%block!=0)
    {
        num=block+1;
    }  
    else num=block; 
    for(int i=1;i<=num;i++)
    {
        l[i]=(i-1)*block+1;
        r[i]=i*block;
    }
    r[num]=n;
    for(int i=1;i<=num;i++)
    sort(b+l[i],b+r[i]+1);
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
    }
}
void ybh(int x,int c)//单点修改，暴力即可
{
    a[x]=c;
    for(int i=l[belong[x]];i<=r[belong[x]];i++)
    b[i]=a[i];
    sort(b+l[belong[x]],b+r[belong[x]]+1);
}
int getnum(int x,int v)//块内二分
{
    int ln=l[x],rn=r[x],mid;
    while(ln<=rn)
    {
        mid=ln+rn>>1;
        if(b[mid]<v) ln=mid+1;
        else rn=mid-1;
    }
    return ln-l[x];
}
int pd(int x,int y,int v)//分块验证
{
    int res=0;
    if(belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++)
        {
            if(a[i]<v)
            res++;
        }
        return res;
    }
    for(int i=x;i<=r[belong[x]];i++)
    {
        if(a[i]<v) res++;
    }
    for(int i=l[belong[y]];i<=y;i++)
    {
        if(a[i]<v) res++;
    }
    for(int i=belong[x]+1;i<belong[y];i++)
      res+=(getnum(i,v));//分块区间再2分
      return res;
}
int qu(int x,int y,int k)//二分就第k小
{
    int res=0,l=0,r=1e9,mid;
    while(l<=r)
    {
        mid=l+r>>1;
        cout<<pd(x,y,mid)<<endl;
        if(pd(x,y,mid)<k)
        l=mid+1;
        else 
        {
            r=mid-1;
            res=mid;
        }
    }
    return res-1;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        a[i]=getint();
        b[i]=a[i];
    }   
    block=sqrt(n);
    build();
    for(int i=1;i<=m;i++)
    {
        char s;
        int lx,ly,kk;
        cin>>s;
        if(s=='Q')
        {
            lx=getint();
            ly=getint();
            kk=getint();
            cout<<qu(lx,ly,kk)<<endl;
        }
        else {
            scanf("%lld%lld",&lx,&kk);
            ybh(lx,kk);
        }
    }
    return 0;
}