ZOJ 2112 Dynamic Rankings(带修改的主席树)
Dynamic Rankings
Time Limit: 10 Seconds Memory Limit: 32768 KB
The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.
Your task is to write a program for this computer, which
- Reads N numbers from the input (1 <= N <= 50,000)
- Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.
Input
The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.
The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format
Q i j k or
C i t
It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.
There're NO breakline between two continuous test cases.
Output
For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])
There're NO breakline between two continuous test cases.
Sample Input
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
3
6
题意:
n个数，q个询问 (n<=50000, q<=10000)
Q x y z 代表询问[x, y]区间里的第z小的数
C x y 代表将(从左往右数)第x个数变成y
解析:
我看了大神讲半天看不懂，就直接啃代码，边看代码，边看题解
总的简单总结一下就是
树状数组维护的主席树(线段树)
就优化了前缀和的性质
最普通的主席树，i的前缀和树是用root[i]来存的
但是用树状数组,就是用
for(;i>0;i-=lowbit(i)) use[i]=s[j];
这几棵树共同存储i的前缀和树
这样虽然看上去有点多此一举，但是可以用于带修改的主席树。
因为修改一个点j，按照普通的主席树，你需要修改root[j,n]中
的树，这样复杂度就会变大，用树状数组优化你就只需要更新
for(i=j;i<=n;i+=lowbit(i)) 这几颗树就可以了。
use就像一个卡带一样，只有当前需要计算的树它才会留有孔，
不需要的树就没有孔，又因为这些树的结构都是一样的,
所以相当于在一颗树上移动一样，移动到左孩子，对应卡带就会移动
对于这里的更新主席树中的一棵树root[x]，我们肯定要把x的历史版本
past=root[x]给放弃掉，而不是像初始的建树的时候还进行迭代保存
(即root[x]=past,root[x]=newroot)。因为这里root[x]就是以序列下标为
key,而不是版本的次序，并且对于历史版本对于这道题根本没有任何用处
。所以就直接丢弃。
#include <bits/stdc++.h>
#define lowbit(x) ( x&( -x ) )
using namespace std;
typedef long long ll;
const int MAXN = 5e4+110;
const int M = 1e4+100;
int n,m;
ll a[MAXN];
ll ran[MAXN*2];
struct node
{
char id;
int l,r,k;
}Q[M];
int rt[MAXN],ls[MAXN*50],rs[MAXN*50],tot,sz;
int sum[MAXN*50];
int use[MAXN],S[MAXN];
int RIGHT,LEFT;
int getSum(int pos) //区间查询
{
int ans=0;
while(pos)
{
ans+=sum[ls[use[pos]]]; //找第k小的数首先判断左区间
pos-=lowbit(pos);
}
return ans;
}
void build(int& root,int l,int r)
{
root=++tot;
sum[root]=0;
if(l==r) return;
int mid=(l+r)>>1;
build(ls[root],l,mid);
build(rs[root],mid+1,r);
}
void update(int& root,int l,int r,int last,int x,int val)
{
root=++tot;
ls[root]=ls[last];
rs[root]=rs[last];
sum[root]=sum[last]+val;
if(l==r) return ;
int mid=(l+r)>>1;
if(mid>=x) update(ls[root],l,mid,ls[last],x,val);
else update(rs[root],mid+1,r,rs[last],x,val);
}
int query(int ss,int tt,int l,int r,int k) //第k小
{
if(l==r) return l;
int rest=getSum(RIGHT)-getSum(LEFT);
int cnt=sum[ls[tt]]-sum[ls[ss]];
cnt+=rest;
int mid=(l+r)>>1;
if(k<=cnt)
{
for(int j=RIGHT;j>0;j-=lowbit(j)) use[j]=ls[use[j]]; //进入1..RIGHT的前缀和树当前区间的左区间
for(int j=LEFT;j>0;j-=lowbit(j)) use[j]=ls[use[j]]; //进入1..LEFT的前缀和树当前区间的左区间
return query(ls[ss],ls[tt],l,mid,k);
}
else
{
for(int j=RIGHT;j>0;j-=lowbit(j)) use[j]=rs[use[j]]; //进入1..RIGHT的前缀和树当前区间的右区间
for(int j=LEFT;j>0;j-=lowbit(j)) use[j]=rs[use[j]]; //进入1..LEFT的前缀和树当前区间的右区间
return query(rs[ss],rs[tt],mid+1,r,k-cnt);
}
}
void input()
{
sz=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
ran[++sz]=a[i];
}
for(int i=1;i<=m;i++){
getchar();
scanf("%c",&Q[i].id);
if(Q[i].id=='Q'){
scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k);
} else{
scanf("%d%d",&Q[i].l,&Q[i].k);
ran[++sz]=Q[i].k;
}
}
tot=0;
sort(ran+1,ran+1+sz);
sz=unique(ran+1,ran+1+sz)-(ran+1);
build(rt[0],1,sz);
for(int i=1;i<=n;i++)
{
int pos=lower_bound(ran+1,ran+1+sz,a[i])-ran;
update(rt[i],1,sz,rt[i-1],pos,1);
}
for(int i=1;i<=n;i++) //一开始全为空树
S[i]=rt[0];
}
void Change(int x,int pos,int val) //单点更新
{
int past;
while(x<=n)
{
past=S[x];
update(S[x],1,sz,past,pos,val);
x+=lowbit(x);
}
}
void solve()
{
for(int i=1;i<=m;i++)
{
if(Q[i].id=='Q'){
RIGHT=Q[i].r;
LEFT=Q[i].l-1;
for(int j=RIGHT;j>0;j-=lowbit(j)) use[j]=S[j]; //记录1..RIGHT的前缀和树
for(int j=LEFT;j>0;j-=lowbit(j)) use[j]=S[j]; //记录1..LEFT的前缀和树
//use用于遍历树状数组表示的每一棵树
//user[j]表示第j棵树已经遍历到它的编号为use[j]的点
int ind=query(rt[Q[i].l-1],rt[Q[i].r],1,sz,Q[i].k);
printf("%lld\n",ran[ind]);
} else{
int pos=lower_bound(ran+1,ran+1+sz,a[Q[i].l])-ran;
Change(Q[i].l,pos,-1);
pos=lower_bound(ran+1,ran+1+sz,Q[i].k)-ran;
Change(Q[i].l,pos,1);
a[Q[i].l]=Q[i].k;
}
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
input();
solve();
}
}