BZOJ1901：Zju2112 Dynamic Rankings—

http://www.lydsy.com/JudgeOnline/problem.php?id=1901

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继续回答上面的问题。

Input

第一行有两个正整数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

m,n≤10000

Output

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

————————————————————————————

UPT：18.4.2美化代码，删改题解。

带修改主席树板子题目（bzoj真喜欢权限板子题）

然后我学了一上午：https://www.cnblogs.com/candy99/p/6166467.html

总的来说如果我们暴力修改主席树的话，我们对于每一棵主席树都需要进行修改，那么这样时间复杂度就爆棚了。

而我们考虑，树状数组和线段树的修改仅仅只是logn的。

所以我们试着让树状数组套上主席树，这样就能方便的修改值了。

也就是说，树状数组的每一个节点都挂着一棵主席树，这样所需要修改的主席树就变成O(logn)棵了。

那么查询也很简单，就是树状数组的查询方法（因为我们外层包的是树状数组，所以查询就是在查主席树的根，也就不需要主席树了）。

显然空间复杂度为O(nlognlogn)

！但是！我学的那篇博客提供了一种O(2nlogn)的做法。

我们直接将修改操作另开一棵树状数组（upt：其实是开一个主席树然后用树状数组的lowbit修改）维护，这样就变成了两个主席树了，查询的时候两者的和一加即可。

注意事项：

1.注意区分两个主席树，本代码中rt为原序列主席树，root为存修改的主席树。

2.空间记得根据空间复杂度开。

3.不要用什么玄学的stl，不然AC变TLE就是一瞬间的事情。

4.离散化。

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

const int N=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct tree{

    int l,r,sum;

}tr[N*];

struct question{

    char s[];

    int i,j,k,t;

}q[N];

int a[N],b[N],rt[N],root[N],n,m,Q,pool;

int q1[N],t1,q2[N],t2;

inline void initLSH(){

    sort(b+,b+m+);

    m=unique(b+,b+m+)-b-;

    return;

}

inline int LSH(int v){return lower_bound(b+,b+m+,v)-b;}

inline int lowbit(int x){return x&-x;}

inline void insert(int y,int &x,int l,int r,int p,int v){

    tr[x=++pool]=tr[y];

    tr[x].sum+=v;

    if(l==r)return;

    int mid=(l+r)>>;

    if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p,v);

    else insert(tr[y].r,tr[x].r,mid+,r,p,v);

}

inline void add(int pos,int v){

    int p=LSH(a[pos]);

    for(int i=pos;i<=n;i+=lowbit(i))insert(root[i],root[i],,m,p,v);

    //注意这里是root

}

inline int cal(){

    int sum1=,sum2=;

    for(int i=;i<=t1;i++)sum1+=tr[tr[q1[i]].l].sum;

    for(int i=;i<=t2;i++)sum2+=tr[tr[q2[i]].l].sum;

    return sum2-sum1;

}

inline int query(int nl,int nr,int k){

    int l=,r=m;t1=t2=;

    for(int i=nl;i;i-=lowbit(i))q1[++t1]=root[i];

    for(int i=nr;i;i-=lowbit(i))q2[++t2]=root[i];

    //注意这里是root

    nl=rt[nl],nr=rt[nr];

    //注意这里是rt

    while(l<r){

    int ls=cal()+tr[tr[nr].l].sum-tr[tr[nl].l].sum;

    int mid=(l+r)>>;

    if(k<=ls){

        for(int i=;i<=t1;i++)q1[i]=tr[q1[i]].l;

        for(int i=;i<=t2;i++)q2[i]=tr[q2[i]].l;

        nl=tr[nl].l;nr=tr[nr].l;

        r=mid;

    }else{

        for(int i=;i<=t1;i++)q1[i]=tr[q1[i]].r;

        for(int i=;i<=t2;i++)q2[i]=tr[q2[i]].r;

        nl=tr[nl].r;nr=tr[nr].r;

        l=mid+;k-=ls;

    }

    }

    return l;

}

int main(){

    n=read();

    Q=read();

    for(int i=;i<=n;i++)a[i]=b[++m]=read();

    for(int i=;i<=Q;i++){

    scanf("%s",q[i].s);

    if(q[i].s[]=='Q'){

        q[i].i=read();q[i].j=read();q[i].k=read();

    }

    else{

        q[i].i=read();

        q[i].t=b[++m]=read();

    }

    }

    initLSH();

    for(int i=;i<=n;i++)insert(rt[i-],rt[i],,m,LSH(a[i]),);

    //注意这里是rt

    for(int i=;i<=Q;i++){

    if(q[i].s[]=='Q')

        printf("%d\n",b[query(q[i].i-,q[i].j,q[i].k)]);

    else{

        add(q[i].i,-);

        a[q[i].i]=q[i].t;

        add(q[i].i,);

    }

    }

    return ;

}

巴特西

BZOJ1901：Zju2112 Dynamic Rankings——题解

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章