ZOJ 2112 线段树+平衡树

题意：

N<=50000 M<=10000

给定一个数组A[1]~A[N]，有M个操作

每个操作可以如下

Q i j t 输出 A[I]~A[J]之间第t小的数

C i t 将A[I]赋值为t

解题分析：

线段树套一个平衡树，然后二分答案。

利用线段树和平衡树来求区间内<=这个数的数的个数。

复杂度O(M(lgN)^3)

code：

#include #include #define L(x) ((x)*2)
#define R(x) ((x)*2+1)
#define N 1000001
#define INF 0x7FFFFFFF/2-10
#define min(x,y) (x)<(y)?(x):(y)

struct SbtTreeType{int l,r,s,w;}tr[N];
struct InterZoneType{int l,r,root;}T[N];
int a[N],n,m,tot;

void Left(int &p){
    int t=tr[p].r;
    tr[p].r=tr[t].l;
    tr[t].l=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void Right(int &p){
    int t=tr[p].l;
    tr[p].l=tr[t].r;
    tr[t].r=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void repair(int &p){
    bool flag=false;
    if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
        Left(tr[p].l);
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
        Left(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
        Right(tr[p].r);
        Left(p);
        flag=true;
    }
    if (flag){
        repair(tr[p].l);
        repair(tr[p].r);
        repair(p);
    }
}

void ins(int &p,int w){
    if (p==0){
        tr[++tot].l=0;
        tr[tot].r=0;
        tr[tot].s=1;
        tr[tot].w=w;
        p=tot;
        return;
    }
    if (w<=tr[p].w) ins(tr[p].l,w);
               else ins(tr[p].r,w);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

int del(int &p,int w){
    tr[p].s–;
    if (tr[p].w==w || tr[p].l==0 && w<=tr[p].w || tr[p].r==0 && w>tr[p].w){
        int delnum=tr[p].w;
        if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
        else tr[p].w=del(tr[p].l,0x7FFFFFFF);
        return delnum;
    }
    if (w<=tr[p].w) return del(tr[p].l,w);
               else return del(tr[p].r,w);
}

void Build(int p,int l,int r){
    T[p].l=l; T[p].r=r; T[p].root=0;
    int i;
    for (i=l;i<=r;i++) ins(T[p].root,a[i]);
    if (l        int mid=(l+r)/2;
        Build(L(p),l,mid);
        Build(R(p),mid+1,r);
    }
}

void Change(int p,int pos,int pre,int key){
    if (pos    del(T[p].root,pre);
    ins(T[p].root,key);
    if (T[p].l        Change(L(p),pos,pre,key);
        Change(R(p),pos,pre,key);
    }
}

int rank(int p,int w){
    if (p==0) return 0;
    if (w    return (tr[tr[p].l].s+1+rank(tr[p].r,w));
}

int Getnum(int p,int l,int r,int x){
    if (r    if (l<=T[p].l && T[p].r<=r) return rank(T[p].root,x);
    int tx=Getnum(L(p),l,r,x),ty=Getnum(R(p),l,r,x);
    return (tx+ty);
}

void work(){
    int i;
    tot=0;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    Build(1,1,n);
    char ch;
    int il,ir,dj,x,y,l,r,mid;
    for (i=1;i<=m;i++){
        scanf("%c",&ch);
        while (ch==10 || ch==13) scanf("%c",&ch);
        if (ch!=’C’){
            scanf("%d%d%d",&il,&ir,&dj);
            l=-INF;
            r=INF;
            while (l                mid=(l+r)/2;
                if (Getnum(1,il,ir,mid)                                       else r=mid;
            }
            printf("%dn",l);
        }
        else {
            scanf("%d%d",&x,&y);
            Change(1,x,a[x],y);
            a[x]=y;
        }
    }
}

int main(){
    int TC;
    scanf("%d",&TC);
    int i;
    for (i=1;i<=TC;i++)
      work();
    return 0;
}