【权值线段树】bzoj3224 Tyvj 1728 普通平衡树

一个板子。

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100001
struct Data
{
    int v,p;
}t[N];
bool cmp(const Data &a,const Data &b)
{
    return a.v<b.v;
}
int T[N<<2],op[N],a[N],n,ma[N],e;
void Update(int p,int v,int rt,int l,int r)//插入删除
{
    T[rt]+=v;
    if(l==r) return;
    int m=(l+r>>1);
    if(p<=m) Update(p,v,rt<<1,l,m);
    else Update(p,v,rt<<1|1,m+1,r);
}
int Kth(int K,int rt,int l,int r)//K小值
{
    if(l==r) return l;
    int m=(l+r>>1);
    if(T[rt<<1]>=K) return Kth(K,rt<<1,l,m);
    return Kth(K-T[rt<<1],rt<<1|1,m+1,r);
}
int Rank(int p,int rt,int l,int r)//排名
{
    if(r<p) return T[rt];
    int m=(l+r>>1),res=0;
    res+=Rank(p,rt<<1,l,m);
    if(m<p-1) res+=Rank(p,rt<<1|1,m+1,r);
    return res;
}
int Findp(int rt,int l,int r)
{
    if(l==r) return l;
    int m=(l+r>>1);
    if(T[rt<<1|1]) return Findp(rt<<1|1,m+1,r);
    return Findp(rt<<1,l,m);
}
int Pre(int p,int rt,int l,int r)
{
    if(r<p)
      {
          if(T[rt]) return Findp(rt,l,r);
          return 0;
      }
    int m=(l+r>>1),Re;
    if(m<p-1 && T[rt<<1|1] && (Re=Pre(p,rt<<1|1,m+1,r))) return Re;
    return Pre(p,rt<<1,l,m);
}
int Findn(int rt,int l,int r)
{
    if(l==r) return l;
    int m=(l+r>>1);
    if(T[rt<<1]) return Findn(rt<<1,l,m);
    return Findn(rt<<1|1,m+1,r);
}
int Nex(int p,int rt,int l,int r)
{
    if(p<l)
      {
          if(T[rt]) return Findn(rt,l,r);
          return 0;
      }
    int m=(l+r>>1),Re;
    if(p<m && T[rt<<1] && (Re=Nex(p,rt<<1,l,m))) return Re;
    return Nex(p,rt<<1|1,m+1,r);
}
int main()
{
//    freopen("bzoj3224.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
      {
          scanf("%d%d",&op[i],&t[i].v);
          t[i].p=i;
      }
    sort(t+1,t+1+n,cmp);
    ma[a[t[1].p]=++e]=t[1].v;
    for(int i=2;i<=n;i++)
      {
        if(t[i].v!=t[i-1].v) ++e;
        ma[a[t[i].p]=e]=t[i].v;
      }
    for(int i=1;i<=n;i++)
      {
        if(op[i]==1) Update(a[i],1,1,1,e);
        else if(op[i]==2) Update(a[i],-1,1,1,e);
        else if(op[i]==3) printf("%d
",Rank(a[i],1,1,e)+1);
        else if(op[i]==4) printf("%d
",ma[Kth(ma[a[i]],1,1,e)]);
        else if(op[i]==5) printf("%d
",ma[Pre(a[i],1,1,e)]);
        else printf("%d
",ma[Nex(a[i],1,1,e)]);
      }
    return 0;