BruceJay's Blog

BZOJ1901 Zju2112 Dynamic Rankings

| Comments

To start with

线段树都不会的Bruce开始了可持久化线段树的学习。

  • 都去看看陈老师的论文咯 可持久化线段树要支持历史版本的运作。 修改时一个位置时,只会修改线段树上的一条链(logn个点),于是每次只需新建logn个点。 可持久化线段树(主席树)可以做什么呢:比如区间第k大啦(无论修改不修改),树上路径第k大啦。。。

Problem

Solution

这一题就是带修改的区间第k大问题。
这里的每棵权值线段树维护的只是某一个位置,前缀和的维护用树状数组完成。
询问时在线段树上二分就是了。
建议先离散化。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20100;
const int Size = 2200100;
struct node{char s[1];int x,y,k;}q[N];
int a[N]; int c[N]; int root[N];
int tr[Size][2]; int sum[Size];
int L[N]; int R[N];
int n,m,cnt=0,sz=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int Find(int x)
{
    int l=1,r=cnt,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(c[mid]>=x) r=mid-1,ans=mid;
        else l=mid+1;
    }
    return ans;
}

void Update(int last,int l,int r,int &t,int pos,int val)
{
    if(!t) t=++sz;   sum[t]=sum[last]+val;
    tr[t][0]=tr[last][0]; tr[t][1]=tr[last][1];
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) Update(tr[last][0],l,mid,tr[t][0],pos,val);
    else Update(tr[last][1],mid+1,r,tr[t][1],pos,val);
}

void Modify(int x,int pos,int val)
{
    for(int i=x;i<=n;i+=(i&-i)){
        Update(root[i],1,cnt,root[i],pos,val);
    }
}

int Query(int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int suml=0,sumr=0;
    for(int i=1;i<=L[0];i++) suml+=sum[tr[L[i]][0]];
    for(int i=1;i<=R[0];i++) sumr+=sum[tr[R[i]][0]];
    int delta=sumr-suml;
    if(delta>=k){
        for(int i=1;i<=L[0];i++) L[i]=tr[L[i]][0];
        for(int i=1;i<=R[0];i++) R[i]=tr[R[i]][0];
        return Query(l,mid,k);
    }
    else{
        for(int i=1;i<=L[0];i++) L[i]=tr[L[i]][1];
        for(int i=1;i<=R[0];i++) R[i]=tr[R[i]][1];
        return Query(mid+1,r,k-delta);
    }
}

int Ask(int l,int r,int k)
{
    L[0]=R[0]=0;
    for(int i=l;i;i-=(i&-i)) L[++L[0]]=root[i];
    for(int i=r;i;i-=(i&-i)) R[++R[0]]=root[i];
    return Query(1,cnt,k);
}

int main()
{
    freopen("1901.in","r",stdin);
    freopen("1901.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        c[++cnt]=a[i];
    }
    for(int i=1;i<=m;i++){
        scanf("%s",q[i].s);
        q[i].x=read(); q[i].y=read();
        if(q[i].s[0]=='Q') q[i].k=read();
        else c[++cnt]=q[i].y;
    }
    sort(c+1,c+cnt+1);
    int tot=1;
    for(int i=2;i<=cnt;i++)
        if(c[i]!=c[tot]) c[++tot]=c[i];
    cnt=tot;
    for(int i=1;i<=n;i++){
        int pos=Find(a[i]);
        Modify(i,pos,1);
    }
    for(int i=1;i<=m;i++){
        if(q[i].s[0]=='Q'){
            int pos=Ask(q[i].x-1,q[i].y,q[i].k);
            printf("%d\n",c[pos]);
        }
        else{
            int pos=Find(a[q[i].x]);
            Modify(q[i].x,pos,-1);
            a[q[i].x]=q[i].y; pos=Find(q[i].y);
            Modify(q[i].x,pos,1);
        }
    }
    return 0;
}

Last but not least

感觉还是不太理解可持久化线段树啊!!!
至少要我讲,,,我讲不出。

Comments

comments powered by Disqus