题目
给定一个含有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=
10000+
20;
struct node{
int l,r;
int sum;
int lc,rc;
}tree[maxn
*500];
int cnt;
int n,
m;
int a[maxn];
int num[maxn],tot=
0;
int q[maxn][
4];
int h[maxn],N=
0;
int init()
{
scanf(
"%d%d",&n,&
m);
for (
int i=
1;i<=n;i++)
{
scanf(
"%d",&a[i]),num[++tot]=a[i];
}
for (
int i=
1;i<=
m;i++)
{
char c;
cin>>c;
if (c==
'Q')
{
q[i][
0]=
1;
scanf(
"%d%d%d",&
q[i][
1],&
q[i][
2],&
q[i][
3]);
}
else
{
q[i][
0]=
0;
scanf(
"%d%d",&
q[i][
1],&
q[i][
2]);
num[++tot]=
q[i][
2];
}
}
sort(num+
1,num+
1+tot);
h[++N]=num[
1];
for (
int i=
2;i<=tot;i++)
if (num[i-
1]!=num[i]) h[++N]=num[i];
}
int lowbit(
int x) {
return x&(-
x);}
int nownode(
int last,
int add)
{
cnt++;
tree[cnt]=tree[
last];
tree[cnt].sum+=add;
return cnt;
}
void insert(
int &
x,
int y,
int k,
int add)
{
x=nownode(
y,add);
if (tree[
x].l==tree[
x].r)
return;
int mid=(tree[
x].l+tree[
x].r)/
2;
if (mid>=k) insert(tree[
x].
lc,tree[
y].
lc,k,add);
else insert(tree[
x].rc,tree[
y].rc,k,add);
}
int l[maxn],r[maxn];
int find(
int L,
int R,
int k)
{
if (L==R)
return L;
int numl=
0,numr=
0,mid=(L+R)>>
1;;
for (
int i=
1;i<=l[
0];i++) numl+=tree[tree[l[i]].
lc].sum;
for (
int i=
1;i<=r[
0];i++) numr+=tree[tree[r[i]].
lc].sum;
if (numr-numl>=k)
{
for (
int i=
1;i<=l[
0];i++) l[i]=tree[l[i]].
lc;
for (
int i=
1;i<=r[
0];i++) r[i]=tree[r[i]].
lc;
return find(L,mid,k);
}
else
{
for (
int i=
1;i<=l[
0];i++) l[i]=tree[l[i]].rc;
for (
int i=
1;i<=r[
0];i++) r[i]=tree[r[i]].rc;
return find(mid+
1,R,k-numr+numl);
}
}
void build(
int &
x,
int l,
int r)
{
x=++cnt;
tree[
x].sum=
0;
tree[
x].l=l,tree[
x].r=r;
if (l==r)
return;
int mid=(l+r)/
2;
build(tree[
x].
lc,l,mid);
build(tree[
x].rc,mid+
1,r);
return;
}
int root[maxn];
int main()
{
init();
build(root[
0],
1,N);
for (
int i=
1;i<=n;i++) root[i]=root[
0];
for (
int i=
1;i<=n;i++)
{
int K=lower_bound(h+
1,h+N+
1,a[i])-h;
for (
int j=i;j<=n;j+=lowbit(j)) insert(root[j],root[j],K,
1);
}
for (
int i=
1;i<=
m;i++)
{
if (
q[i][
0])
{
l[
0]=r[
0]=
0;
q[i][
1]--;
for (
int j=
q[i][
1];j>
0;j-=lowbit(j)) l[++l[
0]]=root[j];
for (
int j=
q[i][
2];j>
0;j-=lowbit(j)) r[++r[
0]]=root[j];
printf(
"%d\n",h[find(
1,N,
q[i][
3])]);
}
else
{
int K=lower_bound(h+
1,h+N+
1,a[
q[i][
1]])-h;
for (
int j=
q[i][
1];j<=n;j+=lowbit(j))
insert(root[j],root[j],K,-
1);
a[
q[i][
1]]=
q[i][
2];
K=lower_bound(h+
1,h+N+
1,
q[i][
2])-h;
for (
int j=
q[i][
1];j<=n;j+=lowbit(j))
insert(root[j],root[j],K,
1);
}
}
}
