1901: Zju2112 Dynamic Rankings
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。
BIT套权值线段树
wy表示把离散化的数组开小了，查了一上午错/(ㄒoㄒ)/~~。。。
#include<cstdio>
#include<algorithm>
#define MaxN 10010
#define MaxT 1000010
using namespace std;
int N,M,Q,tot;
int A[MaxN],Li[2*MaxN];
int Que[2][MaxN];
int root[MaxN];
int ord[MaxN];
int st[MaxN],en[MaxN],Num[MaxN];
struct point{
int l,r,sum;
point(int x=0,int y=0,int s=0){
l=x; r=y; sum=s;
}
}P[MaxT];
int Get(){
char Ch;
int Sign=1,Num;
while ((Ch=getchar())<'0'||Ch>'9')
if (Ch=='-') Sign=-1;
Num=Ch-'0';
while ((Ch=getchar())>='0'&&Ch<='9')
Num=Num*10+Ch-'0';
return Sign*Num;
}
void Discretization(){
sort(Li+1,Li+M+1);
M=unique(Li+1,Li+M+1)-Li-1;
for (int i=1;i<=N;++i){
int x=A[i];
A[i]=lower_bound(Li+1,Li+M+1,A[i])-Li;
}
for (int i=1;i<=Q;++i)
if (!ord[i]){
int x=Num[i];
Num[i]=lower_bound(Li+1,Li+M+1,Num[i])-Li;
}
}
int lowbit(int x){
return x & (-x);
}
void Insert(int &x,const int &l,const int &r,const int &p){
if (!x) x=++tot;
++P[x].sum;
if (l==r) return;
int mid=(l+r)/2;
if (p<=mid) Insert(P[x].l,l,mid,p);
else Insert(P[x].r,mid+1,r,p);
}
void Reduce(const int &x,const int &l,const int &r,const int &p){
--P[x].sum;
if (l==r) return;
int mid=(l+r)/2;
if (p<=mid) Reduce(P[x].l,l,mid,p);
else Reduce(P[x].r,mid+1,r,p);
}
void Add(int x,int s){
for (;x<=N;x+=lowbit(x))
Insert(root[x],1,M,s);
}
void Delete(int x,int s){
for (;x<=N;x+=lowbit(x))
Reduce(root[x],1,M,s);
}
void find(int x,int k){
Que[k][0]=0;
for (;x;x-=lowbit(x))
Que[k][++Que[k][0]]=root[x];
}
void Query(int l,int r,int c){
find(l,0);
find(r,1);
int Ans;
int L=1,R=M;
for (;;){
if (L==R) {
Ans=L;
break;
}
int mid=L+R>>1;
int tmp=0;
for (int i=1;i<=Que[1][0];++i)
tmp+=P[P[Que[1][i]].l].sum;
for (int i=1;i<=Que[0][0];++i)
tmp-=P[P[Que[0][i]].l].sum;
if (tmp>=c){
R=mid;
for (int i=1;i<=Que[1][0];++i)
Que[1][i]=P[Que[1][i]].l;
for (int i=1;i<=Que[0][0];++i)
Que[0][i]=P[Que[0][i]].l;
}
else{
L=mid+1;
for (int i=1;i<=Que[1][0];++i)
Que[1][i]=P[Que[1][i]].r;
for (int i=1;i<=Que[0][0];++i)
Que[0][i]=P[Que[0][i]].r;
c-=tmp;
}
}
printf("%d\n",Li[Ans]);
}
int main(){
scanf("%d%d",&N,&Q);
for (int i=1;i<=N;++i)
A[i]=Li[++M]=Get();
char Ch;
for (int i=1;i<=Q;++i){
while ((Ch=getchar())<'A'||Ch>'Z');
if (Ch=='Q'){
ord[i]=1;
st[i]=Get(); en[i]=Get();
Num[i]=Get();
}
else {
ord[i]=0;
st[i]=Get();
Num[i]=Li[++M]=Get();
}
}
Discretization();
for (int i=1;i<=N;++i)
Add(i,A[i]);
for (int i=1;i<=Q;++i)
if (ord[i])
Query(st[i]-1,en[i],Num[i]);
else{
Delete(st[i],A[st[i]]);
Add(st[i],Num[i]);
A[st[i]]=Num[i];
}
}
评论 (0)
