题目
给定一个含有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，然后读入一系列的指令，包括询问指令和修改指令。
对于每一个询问指令，你必须输出正确的回答。
分析
用分块的写法，分块可真是暴力啊
ps：修改了一个傻逼错误
链接
code
using namespace std;
const
int maxn=
20000+
20;
int a[maxn],b[maxn];
int cnt,size;
int belong[maxn];
int n,
m;
int MIN,MAX;
int b_s(
int l,
int r,
int K)
{
while(l!=r)
{
int m=(l+r)>>
1;
if(a[
m]>=K) r=
m;
else l=
m+
1;
}
if(a[l]>=K)--l;
return l;
}
int find(
int l,
int r,
int K)
{
int L=belong[l],R=belong[r];
int x=MIN,
y=MAX+
1;
while (
x<
y)
{
int mid=(
x+
y)/
2,num=
0;
if (L==R)
{
num=
0;
for (
int i=l;i<=r;i++)
if (b[i]<mid) num++;
}
else
{
num=
0;
for (
int i=l;i<=L
*size;i++)
if (b[i]<mid) num++;
for (
int i=(R-
1)
*size+
1;i<=r;i++)
if (b[i]<mid) num++;
for (
int i=L+
1;i<R;i++)
num+=b_s((i-
1)
*size+
1,i
*size,mid)-(i-
1)
*size;
}
if (num>=K)
y=mid;
else x=mid+
1;
}
return x-
1;
}
int main()
{
scanf(
"%d%d",&n,&
m);
MIN=
2000000000; MAX=-MIN;
for (
int i=
1;i<=n;i++)
{
scanf(
"%d",&a[i]);
b[i]=a[i];
if (a[i]<MIN) MIN=a[i];
if (a[i]>MAX) MAX=a[i];
}
size=
sqrt(n);
for (
int i=
1;i<=n;i++)
{
belong[i]=(i-
1)/size+
1;
}
cnt=belong[n];
for (
int i=
1;i<cnt;i++)
sort(a+(i-
1)
*size+
1,a+min(i
*size,n)+
1);
for (
int i=
1;i<=
m;i++)
{
char c;
cin>>c;
if (c==
'Q')
{
int l,r,
x;
scanf(
"%d%d%d",&l,&r,&
x);
printf(
"%d\n",find(l,r,
x));
}
else
{
int x,
y;
scanf(
"%d%d",&
x,&
y);
if (
y<MIN) MIN=
y;
if (
y>MAX) MAX=
y;
int K=lower_bound(a+(belong[
x]-
1)
*size+
1,a+min(belong[
x]
*size,n)+
1,b[
x])-a;
b[
x]=
y; a[K]=
y;
sort(a+(belong[
x]-
1)
*size+
1,a+min(belong[
x]
*size,n)+
1);
}
}
}
