记录编号	439003	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	LuciFer_T-J	是否通过	通过
代码语言	C++	运行时间	4.158 s
提交时间	2017-08-18 16:14:36	内存使用	38.69 MiB

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
#define Key_value ch[ch[root][1]][0]

const int maxn=5e4+50;
const int maxm=maxn*25;
const int INF=0x3f3f3f3f;
int a[maxn];
int root[maxm],ch[maxm][2],pre[maxm],dat[maxm],num[maxm],siz[maxm];
int n,m;
int tot1,tot2,s[maxm];

void push_down(int r){

}

void push_up(int r){
    siz[r]=siz[ch[r][0]]+siz[ch[r][1]]+num[r];
}

//0 left  1 right
void Rotate(int x,int kind){
    int y=pre[x];
    push_down(y);
    push_down(x);
    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if (pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][kind]=y;
    pre[y]=x;
    push_up(y);
    push_up(x);//模版中没有
}

void Splay(int r,int goal){
    //    push_down(r);
    while (pre[r]!=goal){
        if (pre[pre[r]]==goal){
            //            push_down(pre[r]);
            //            push_down(r);
            Rotate(r,ch[pre[r]][0]==r);
        }
        else {
            //            push_down(pre[pre[r]]);
            //            push_down(pre[r]);
            //            push_down(r);
            int y=pre[r];
            int kind=ch[pre[y]][0]==y;
            if (ch[y][kind]==r){
                Rotate(r,!kind);
                Rotate(r,kind);
            }
            else{
                Rotate(y,kind);
                Rotate(r,kind);
            }
        }
    }
    //    push_up(r);
    // if (goal==0) root=r;
}


int Find(int r,int x){
    while (r){
        if (dat[r]==x) return r;
        if (x<dat[r]){
            if (!ch[r][0]) return r;
            else r=ch[r][0];
        }
        else if (x>dat[r]){
            if (!ch[r][1]) return r;
            else r=ch[r][1];
        }
    }
    return 0;
}


void NewNode(int &r,int fa,int x){
    if (tot2) r=s[tot2--];
    else r=++tot1;
    pre[r]=fa;
    dat[r]=x;
    num[r]=1;
    siz[r]=1;
    ch[r][0]=ch[r][1]=0;
}

void Insert(int &r,int x){
    if (!r){
        NewNode(r,0,x);
        return ;
    }
    int k=Find(r,x);
  //  Splay(k,0);
  //  r=k;
    int kk=0;
    if (dat[k]==x){
        num[k]++;
        kk=k;
    }
    else if (x<dat[k]){
        NewNode(ch[k][0],k,x);
        kk=ch[k][0];
    }
    else {
        NewNode(ch[k][1],k,x);
        kk=ch[k][1];
    }
    while (k){
        siz[k]++;
        k=pre[k];
    }
    Splay(kk,0);
    r=kk;
}

void Delete(int &r,int x){
    int k=Find(r,x);
    Splay(k,0);
    r=k;
    if (num[k]>1){
        num[k]--;
        siz[k]--;
        return ;
    }
    else{
        if (!ch[r][0]){
            s[++tot2]=r;
            r=ch[r][1];
            pre[r]=0;
            return ;
        }
        else if (!ch[r][1]){
            s[++tot2]=r;
            r=ch[r][0];
            pre[r]=0;
            return ;
        }
        else{
            pre[ch[r][0]]=0;
            int p=Find(ch[r][0],INF);
            Splay(p,0);
            ch[p][1]=ch[r][1];
            pre[ch[r][1]]=p;
            s[++tot2]=r;
            r=p;
            pre[r]=0;
        }
    }
}

void Build(int p,int l,int r){
    for (int i=l;i<=r;i++) Insert(root[p],a[i]);
    if (l==r) return ;
    int mid=(l+r)>>1;
    Build(p*2,l,mid);
    Build(p*2+1,mid+1,r);
}

void Init(){
    memset(root,0,sizeof(root));
    tot1=tot2=0;
    pre[0]=num[0]=dat[0]=ch[0][0]=ch[0][1]=0;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    Build(1,1,n);
}

int Ask_rank(int &r,int x){
    int k=Find(r,x);
    Splay(k,0);
    r=k;
    if (dat[k]>=x) return siz[ch[k][0]];
    else return siz[ch[k][0]]+num[k];
}

int Ask_rank(int p,int l,int r,int L,int R,int x){
    if (L<=l && r<=R){
        return Ask_rank(root[p],x);
    }
    int mid=(l+r)>>1;
    int tmp=0;
    if (L<=mid) tmp+=Ask_rank(p*2,l,mid,L,R,x);
    if (R>mid) tmp+=Ask_rank(p*2+1,mid+1,r,L,R,x);
    return tmp;
}

void Change_add(int p,int l,int r,int x,int y){
    Insert(root[p],y);
    if (l==r) return ;
    int mid=(l+r)>>1;
    if (x<=mid) Change_add(p*2,l,mid,x,y);
    else Change_add(p*2+1,mid+1,r,x,y);
}

void Change_del(int p,int l,int r,int x,int y){
    Delete(root[p],y);
    if (l==r) return ;
    int mid=(l+r)>>1;
    if (x<=mid) Change_del(p*2,l,mid,x,y);
    else Change_del(p*2+1,mid+1,r,x,y);
}

int Ask_pre(int &r,int x){
    int k=Find(r,x);
    Splay(k,0);
    r=k;
    if (dat[k]>=x) {
        if (!ch[k][0]) return -INF;
        int p=Find(ch[k][0],INF);
        Splay(p,0);
        r=p;
        return dat[p];
    }
    else return dat[k];
}


int Ask_pre(int p,int l,int r,int L,int R,int x){
    if (L<=l && r<=R) return Ask_pre(root[p],x);
    int mid=(l+r)>>1;
    int tmp=-INF;
    if (L<=mid) tmp=max(tmp,Ask_pre(p*2,l,mid,L,R,x));
    if (R>mid) tmp=max(tmp,Ask_pre(p*2+1,mid+1,r,L,R,x));
    return tmp;
}

int Ask_succ(int &r,int x){
    int k=Find(r,x);
    Splay(k,0);
    r=k;
    if (dat[k]<=x) {
        if (!ch[k][1]) return INF;
        int p=Find(ch[k][1],-INF);
        Splay(p,0);
        r=p;
        return dat[p];
    }
    else return dat[k];
}

int Ask_succ(int p,int l,int r,int L,int R,int x){
    if (L<=l && r<=R) return Ask_succ(root[p],x);
    int mid=(l+r)>>1;
    int tmp=INF;
    if (L<=mid) tmp=min(tmp,Ask_succ(p*2,l,mid,L,R,x));
    if (R>mid) tmp=min(tmp,Ask_succ(p*2+1,mid+1,r,L,R,x));
    return tmp;
}

int Work(int ll,int rr,int k){
    int l=0,r=1e8;
    while (l<r){
        int mid=(l+r)>>1;
        if (Ask_rank(1,1,n,ll,rr,mid)>=k) r=mid;
        else l=mid+1;
    }
    return l-1;
}

int main(){
    freopen("psh.in","r",stdin);
    freopen("psh.out","w",stdout);
    scanf("%d%d",&n,&m);
    Init();
    // debug();
    while (m--){
        int op;
        int l,r,k;
        scanf("%d",&op);
        if (op==1){
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",Ask_rank(1,1,n,l,r,k)+1);
        }
        else if (op==2){
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",Work(l,r,k));
        }
        else if (op==3){
            scanf("%d%d",&l,&k);
            Change_del(1,1,n,l,a[l]);
            a[l]=k;
            Change_add(1,1,n,l,a[l]);
        }
        else if (op==4){
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",Ask_pre(1,1,n,l,r,k));
        }
        else if (op==5){
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",Ask_succ(1,1,n,l,r,k));
            //          debug();
        }
    }
    return 0;
}