【bzoj3224_2】Tyvj 1728 普通平衡树

2015.04.23 20:30 Thu | 1次阅读 | 旧日oi | 固定链接 | 源码

Description

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个)
  3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数)
  6. 求x的后继(后继定义为大于x,且最小的数)

Input

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数,表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

1.n的数据范围:n<=100000
2.每个数的数据范围:[-1e7,1e7]

题解

学了一下替罪羊树,re,tle了一下午……到了晚上才找到问题,tmd用数组版超级难改,指针版方便一点……但是我不会指针……
bz的数据太水,不重构都能过,我们自己oj上有一个链的情况,于是tle的飞起
看了一下hzwer的3065,写了一个,然后在自己oj上还是tle,然后又自己改了改,终于A掉了!

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 200010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define alpha 0.75
using namespace std;
int n,op,x,tmp;
int a[maxn*10],cnt;
struct ScapeGoatTree
{
    int tail,root,l[maxn],r[maxn],exist[maxn],size[maxn],c[maxn],v[maxn];
    bool isbad(int x)
    {
        return c[l[x]]>c[x]*alpha||c[r[x]]>alpha*c[x];
    }
    void pushup(int x)
    {
        if(!x) return;
        size[x]=exist[x]+size[l[x]]+size[r[x]];
        c[x]=1+c[l[x]]+c[r[x]];
    }
    void Travel(int x)
    {
        if(!x) return;
        Travel(l[x]);
        if(exist[x]) a[++cnt]=x;
        Travel(r[x]);
    }
    void build(int &x,int f,int t)
    {
        if(f>t) 
        {
            x=0;
            return;
        }
        int mid=(f+t)>>1;
        x=a[mid];
        build(l[x],f,mid-1);
        build(r[x],mid+1,t);
        pushup(x);
    }
    void rebuild(int &x)
    {
        cnt=0;Travel(x);
        build(x,1,cnt);
    }
    void insert(int &k,int val)
    {
        if(!k)
        {
            k=++tail;
            v[k]=val;
            size[k]=c[k]=exist[k]=1;
            return;
        }
        size[k]++;c[k]++;
        if(v[k]>=val)insert(l[k],val);
        else insert(r[k],val);
        if(!isbad(k))
        {
            if(tmp)
            {
                if(l[k]==tmp) rebuild(l[k]);
                else rebuild(r[k]);
                tmp=0;
            }
        }
        else tmp=k;
    }
    void erase(int &x,int id)
    {
        if(!x) return;
        if(exist[x]&&id==size[l[x]]+1)
        {
            exist[x]=0;
            size[x]--;
            return;
        }
        size[x]--;
        if(id<=size[l[x]]+exist[x])
            erase(l[x],id);
        else erase(r[x],id-size[l[x]]-exist[x]);
    }
    int rank(int val)
    {
        int x=root,ans=1;
        while(x)
        {
            if(v[x]>=val)x=l[x];
            else
            {
                ans+=size[l[x]]+exist[x];
                x=r[x];
            }
        }
        return ans;
    }
    int get_kth(int k)
    {
        int x=root;
        while(x)
        {
            if(exist[x]&&k==size[l[x]]+1) return v[x];
            else if(size[l[x]]>=k)x=l[x];
            else
            {
                k-=size[l[x]]+exist[x];
                x=r[x];
            }
        }
    }
    void erase(int val)
    {
        erase(root,rank(val));
        if(size[root]<alpha*c[root])
            rebuild(root);
    }
}tree;
int main()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    cin>>n;int now=0;
    while(n--)
    {
        scanf("%d%d",&op,&x);
        if(op==1)tmp=0,tree.insert(tree.root,x);
        else if(op==2) tree.erase(x);
        else if(op==3) printf("%d\n",tree.rank(x));
        else if(op==4) printf("%d\n",tree.get_kth(x));
        else if(op==5) printf("%d\n",tree.get_kth(tree.rank(x)-1));
        else printf("%d\n",tree.get_kth(tree.rank(x+1)));
    }
    return 0;
}```