树阵主席设置树。维护间隔动态K大。
。。
ZOJ到空间太小，太大，仅仅能到BZOJ上交
1901: Zju2112 Dynamic Rankings
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4186 Solved: 1754
[Submit][Status]
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继续回答上面的问题。你须要编一个这种程序，从输入文件里读入序列a。然后读入一系列的指令，包含询问指令和改动指令。对于每个询问指令。你必须输出正确的回答。
第一行有两个正整数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。
Input
对于每一次询问，你都须要输出他的答案。每个输出占单独的一行。
Output
Sample Input
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
6
HINT
20%的数据中，m,n≤100; 40%的数据中，m,n≤1000; 100%的数据中。m,n≤10000。
Source
/**************************************************************
Problem: 1901
User: CKboss
Language: C++
Result: Accepted
Time:488 ms
Memory:55480 kb
****************************************************************/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn=101000;
const int MAXN=2560000; int n,m,tot,q;
int a[maxn],h[maxn];
int T[MAXN],c[MAXN],lson[MAXN],rson[MAXN]; struct Question
{
int kind,l,r,k;
}Q[maxn]; void Init_hash(int k)
{
sort(h,h+k);
m=unique(h,h+k)-h;
} int hash(int x)
{
return lower_bound(h,h+m,x)-h;
} int build(int l,int r)
{
int root=tot++;
if(l!=r)
{
int mid=(l+r)/2;
lson[root]=build(l,mid);
rson[root]=build(mid+1,r);
}
return root;
} int update(int root,int pos,int val)
{
int newroot=tot++,tmp=newroot;
int l=0,r=m-1;
c[newroot]=c[root]+val;
while(l<r)
{
int mid=(l+r)>>1;
if(pos<=mid)
{
lson[newroot]=tot++; rson[newroot]=rson[root];
newroot=lson[newroot]; root=lson[root];
r=mid;
}
else
{
rson[newroot]=tot++; lson[newroot]=lson[root];
newroot=rson[newroot]; root=rson[root];
l=mid+1;
}
c[newroot]=c[root]+val;
}
return tmp;
} int use[maxn*30]; int lowbit(int x)
{
return x&(-x);
} void add(int x,int pos,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
T[i]=update(T[i],pos,val);
} int sum(int x)
{
int ret=0;
for(int i=x;i;i-=lowbit(i))
ret+=c[lson[use[i]]];
return ret;
} int query(int left,int right,int k)
{
int l=0,r=m-1;
for(int i=left-1;i;i-=lowbit(i))
use[i]=T[i];
for(int i=right;i;i-=lowbit(i))
use[i]=T[i];
while(l<r)
{
int mid=(l+r)/2;
int tmp=sum(right)-sum(left-1);
if(tmp>=k)
{
r=mid;
for(int i=left-1;i;i-=lowbit(i))
use[i]=lson[use[i]];
for(int i=right;i;i-=lowbit(i))
use[i]=lson[use[i]];
}
else
{
l=mid+1;
k-=tmp;
for(int i=left-1;i;i-=lowbit(i))
use[i]=rson[use[i]];
for(int i=right;i;i-=lowbit(i))
use[i]=rson[use[i]];
}
}
return l;
} void Init_tree()
{
T[0]=build(0,m-1);
for(int i=1;i<=n;i++)
T[i]=T[0];
for(int i=1;i<=n;i++)
add(i,hash(a[i]),1);
} int main()
{
while(scanf("%d%d",&n,&q)!=EOF)
{
m=0;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
h[m++]=a[i];
}
for(int i=0;i<q;i++)
{
char str[5];
int l,r,k;
scanf("%s",str);
if(str[0]=='Q')
{
scanf("%d%d%d",&l,&r,&k);
Q[i]=(Question){0,l,r,k};
}
else
{
scanf("%d%d",&l,&k);
Q[i]=(Question){1,l,0,k};
h[m++]=k;
}
}
Init_hash(m);
Init_tree();
for(int i=0;i<q;i++)
{
if(Q[i].kind==0)
{
printf("%d\n",h[query(Q[i].l,Q[i].r,Q[i].k)]);
}
else
{
add(Q[i].l,hash(a[Q[i].l]),-1);
add(Q[i].l,hash(Q[i].k),1);
a[Q[i].l]=Q[i].k;
}
}
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。