BZOJ1901 dynamic ranking-带修主席树

题意:

维护一个序列,支持单点修改,区间查询第k小。

Solution:

(普通的主席树相信大家都会,如果没学过建议先去学学再来看这篇文章):
我们回忆一下不带修改的主席树是怎么求出答案的:每一棵主席树维护是前缀和,然后左右端点的主席树差分一下就能求出排名。对于这个问题,我们可以先考虑如何维护一个支持修改的前缀和,显然一个树状数组就可以做到,那么我们类比一下,在主席树上套一个树状数组(即第i棵主席树维护的是(i-lowbit(i),i]这一段区间),就可以达到我们的目的了,注意要先进行离散化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10010;
int n,qe;
struct Q{
int x,y,k;
}q[10010];
struct tree{
int sum,l,r;
}tr[400*N];
int lsh[2*N];
char s[2];
int root[N];
int size,a[N],maxn;
int x,y,tx[30],ty[30],numx,numy;
void update(int &now,int x,int l,int r,int v,int pos)
{
now=++size;
tr[now]=tr[x];
tr[now].sum+=v;
if (l==r) return;
int mid=l+r>>1;
if (pos<=mid) update(tr[now].l,tr[x].l,l,mid,v,pos);
else update(tr[now].r,tr[x].r,mid+1,r,v,pos);
}
void add(int pos,int v)
{
int npos=lower_bound(lsh+1,lsh+1+maxn,a[pos])-lsh;
for (int i=pos;i<=n;i+=(i&-i))
update(root[i],root[i],1,maxn,v,npos);
}
int query(int k,int l,int r)
{
if (l==r) return l;
int lsum=0;
for (int i=1;i<=numx;i++)
lsum-=tr[tr[tx[i]].l].sum;
for (int i=1;i<=numy;i++)
lsum+=tr[tr[ty[i]].l].sum;
int mid=l+r>>1;
if (k>lsum)
{
for (int i=1;i<=numx;i++)
tx[i]=tr[tx[i]].r;
for (int i=1;i<=numy;i++)
ty[i]=tr[ty[i]].r;
query(k-lsum,mid+1,r);
}
else
{
for (int i=1;i<=numx;i++)
tx[i]=tr[tx[i]].l;
for (int i=1;i<=numy;i++)
ty[i]=tr[ty[i]].l;
query(k,l,mid);
}
}
int read()
{
int f=1,x=0;
char ch;
ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-')f=-1;}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
int main()
{
n=read();qe=read();
for (int i=1;i<=n;i++)
a[i]=read(),lsh[++maxn]=a[i];
for (int i=1;i<=qe;i++)
{
scanf("%s",s);
q[i].x=read();q[i].y=read();
if (s[0]=='Q') q[i].k=read();
else lsh[++maxn]=q[i].y;
}
sort(lsh+1,lsh+1+maxn);
maxn=unique(lsh+1,lsh+1+maxn)-lsh-1;
for (int i=1;i<=n;i++) add(i,1);
for (int i=1;i<=qe;i++)
{
if (q[i].k)
{
numx=numy=0;
for (int j=q[i].x-1;j;j-=(j&-j))
tx[++numx]=root[j];
for (int j=q[i].y;j;j-=(j&-j))
ty[++numy]=root[j];
printf("%d\n",lsh[query(q[i].k,1,maxn)]);
}
else add(q[i].x,-1),a[q[i].x]=q[i].y,add(q[i].x,1);
}
}
作者

Fizzmy

发布于

2018-01-06

更新于

2020-11-06

许可协议

评论