[主席树]ZOJ2112 && BZOJ1901 Dynamic Rankings

题意:n个数,q个询问 (n<=50000, q<=10000)

Q x y z 代表询问[x, y]区间里的第z小的数

C x y    代表将(从左往右数)第x个数变成y

上篇介绍了在[x, y]区间内查询第z小的数的方法(静态主席树)

本题有更新操作

若仍用上篇的做法,

每次更新一个数,需要更新的是T[i], T[i+1]... ...T[n](该数所在的树以及它后面的所有树)

因为每棵树T[i]所记录的都是前缀(1到i的数出现的次数) 因此,改变i,会影响i到n的所有树

这样,每次更新的复杂度最坏为O($n$),最坏更新q次即为O($n\times m$) 复杂度相当庞大,很明显这样做是不行的

那怎么办呢?

我们可以发现,对于改变i处的数这个操作,对于T[i], T[i+1]... ...T[n]这些树的影响是相同的

都只改变了  “原来i处的数 的数量”  和  “现在i处的数 的数量” 这两个值而已

我们只要在原来的基础上增加一类树, 用它们来维护更新掉的数

即用树状数组来记录更新,每次更新$logn$棵树

下面来演示一下建树到查询的过程:

比如此题的第一个案例


Q
C
Q

先将序列以及要更新的数(C操作)离散化

即3 2 1 4 7 、 6  ---->(排序) ----> 1 2 3 4 6 7

那么我们就需要建一棵这样的树:[主席树]ZOJ2112 && BZOJ1901 Dynamic Rankings

(圈里的都是结点的编号, 4、5、6、9、10、11号结点代表的分别是1、2、3、4、6、7)

(4、5、9、10你也可以任意作为6或11的儿子, 递归生成的是类似这样的, 这并不重要)

对于3 2 1 4 7(先不管需要更新的6)建完树见下图(建树过程同静态的,不明白的戳这里,上篇博客有讲)

[主席树]ZOJ2112 && BZOJ1901 Dynamic Rankings

(红色的是个数, 相同结点的个数省略了,同前一棵树)

对于C操作之前的Q,就跟静态的类似,减一减 找就好了

然后下面要更新了

对于更新, 我们不改变这些已经建好的树, 而是另建一批树S,用来记录更新,而这批线段树,我们用树状数组来维护

也就是树状数组的每个节点都是一颗线段树

一开始,S[0]、S[1]、S[2]、S[3]、S[4]、S[5](树状数组的每个节点)这些都与T[0]相同(也就是每个节点建了一棵空树)

对于C 2 6 这个操作, 我们只需要减去一个2,加上一个6即可

对于减去2

(树状数组i+lowbit(i)为i的父亲节点, 修改i,就要把i的所有父亲节点都修改了)

2在树状数组中出现的位置是 2、2+lowbit(2)=4 这两个位置,

因此要更新的是S[2]和S[4]这两个节点中的树

删去2后是这样

[主席树]ZOJ2112 && BZOJ1901 Dynamic Rankings

加上一个6 (同样是对于2号位置, 因此需要更新的仍是S[2]和S[4])

加上之后是这样

[主席树]ZOJ2112 && BZOJ1901 Dynamic Rankings

当查询的时候, 对树T的操作与静态的一致,另外再加上S树的值就好了

 #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lson l, m
#define rson m+1, r
const int N=;
int a[N], Hash[N];
int T[N], L[N<<], R[N<<], sum[N<<];
int S[N];
int n, m, tot;
struct node
{
int l, r, k;
bool Q;
}op[]; int build(int l, int r)
{
int rt=(++tot);
sum[rt]=;
if(l!=r)
{
int m=(l+r)>>;
L[rt]=build(lson);
R[rt]=build(rson);
}
return rt;
} int update(int pre, int l, int r, int x, int val)
{
int rt=(++tot);
L[rt]=L[pre], R[rt]=R[pre], sum[rt]=sum[pre]+val;
if(l<r)
{
int m=(l+r)>>;
if(x<=m)
L[rt]=update(L[pre], lson, x, val);
else
R[rt]=update(R[pre], rson, x, val);
}
return rt;
} int lowbit(int x)
{
return x&(-x);
} int use[N];
void add(int x, int pos, int val)
{
while(x<=n)
{
S[x]=update(S[x], , m, pos, val);
x+=lowbit(x);
}
} int Sum(int x)
{
int ret=;
while(x>)
{
ret+=sum[L[use[x]]];
x-=lowbit(x);
}
return ret;
} int query(int u, int v, int lr, int rr, int l, int r, int k)
{
if(l>=r)
return l;
int m=(l+r)>>;
int tmp=Sum(v)-Sum(u)+sum[L[rr]]-sum[L[lr]];
if(tmp>=k)
{
for(int i=u;i;i-=lowbit(i))
use[i]=L[use[i]];
for(int i=v;i;i-=lowbit(i))
use[i]=L[use[i]];
return query(u, v, L[lr], L[rr], lson, k);
}
else
{
for(int i=u;i;i-=lowbit(i))
use[i]=R[use[i]];
for(int i=v;i;i-=lowbit(i))
use[i]=R[use[i]];
return query(u, v, R[lr], R[rr], rson, k-tmp);
}
} void modify(int x, int p, int d)
{
while(x<=n)
{
S[x]=update(S[x], , m, p, d);
x+=lowbit(x);
}
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int q;
scanf("%d%d", &n, &q);
tot=;
m=;
for(int i=;i<=n;i++)
{
scanf("%d", &a[i]);
Hash[++m]=a[i];
}
for(int i=;i<q;i++)
{
char s[];
scanf("%s", s);
if(s[]=='Q')
{
scanf("%d%d%d", &op[i].l, &op[i].r, &op[i].k);
op[i].Q=;
}
else
{
scanf("%d%d", &op[i].l, &op[i].r);
op[i].Q=;
Hash[++m]=op[i].r;
}
}
sort(Hash+, Hash++m);
int mm=unique(Hash+, Hash++m)-Hash-;
m=mm;
T[]=build(, m);
for(int i=;i<=n;i++)
T[i]=update(T[i-], , m, lower_bound(Hash+, Hash++m, a[i])-Hash, );
for(int i=;i<=n;i++)
S[i]=T[];
for(int i=;i<q;i++)
{
if(op[i].Q)
{
for(int j=op[i].l-;j;j-=lowbit(j))
use[j]=S[j];
for(int j=op[i].r;j;j-=lowbit(j))
use[j]=S[j];
printf("%d\n", Hash[query(op[i].l-, op[i].r, T[op[i].l-], T[op[i].r], , m, op[i].k)]);
}
else
{
modify(op[i].l, lower_bound(Hash+, Hash++m, a[op[i].l])-Hash, -);
modify(op[i].l, lower_bound(Hash+, Hash++m, op[i].r)-Hash, );
a[op[i].l]=op[i].r;
}
}
}
return ;
}

ZOJ 2112

上一篇:转载 模板整理 by gc812


下一篇:css简单实现五角星评分、点赞收藏、展示评分(半颗星、1/3颗星)