【BZOJ-3196】二逼平衡树 线段树 + Splay （线段树套平衡树）

3196: Tyvj 1730 二逼平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2271  Solved: 935
[Submit][Status][Discuss]

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行，表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围：n,m<=50000

2.序列中每个数的数据范围：[0,1e8]

3.虽然原题没有，但事实上5操作的k可能为负数

Source

Solution

树套树，线段树套平衡树  其实也可以写  权值线段树套区间线段树

正确姿势就是，对于区间建一颗线段树，线段树的每个区间都建一颗平衡树，对于区间的询问，从线段树上找区间，利用平衡树去询问

操作一：查询区间中的小于K的值，最后+1

操作二：二分判定，代入操作一

操作三：对于包含的每个区间上的pos都修改

操作四：对于每段都查询前驱，最后找到最大的前驱

操作五：对于每段都查询后继，最后找到最小的后继

启发：

认真背模板！！！一条语句的错误浪费了自己和别人很长时间

数据结构题要多练多总结，多调多背

要坚定不移的相信自己是智障，新东西一昧想YY不愿了解别人的方法，就是在作死

大代码题要面向对象编程,合理分成程序段,方便差错和调试

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define maxn 2000100
int n,m,a[maxn],maxx;
//SplayTree-----------------------------------------------------------------------------------------
int fa[maxn],son[maxn][],key[maxn],cnt[maxn],size[maxn],root[maxn],sz;
void clear(int now){son[now][]=son[now][]=fa[now]=cnt[now]=key[now]=size[now]=;}
int get(int now){return son[fa[now]][]==now;}
void update(int now)
{
    if (!now) return;
    size[now]=cnt[now];
    if (son[now][]) size[now]+=size[son[now][]];
    if (son[now][]) size[now]+=size[son[now][]];
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],which=get(x);
    son[y][which]=son[x][which^]; fa[son[y][which]]=y;
    fa[y]=x; son[x][which^]=y; fa[x]=z;
    if (z) son[z][son[z][]==y]=x;
    update(y); update(x);
}
void splay(int rt,int x,int tar)
{
    for (int f; (f=fa[x])!=tar; rotate(x))
        if (fa[f]!=tar)
            rotate(get(x)==get(f)?f:x);
    if (tar==) root[rt]=x;
}
void insert(int rt,int v)
{
    if (!root[rt])
        {sz++;son[sz][]=son[sz][]=fa[sz]=;key[sz]=v;size[sz]=;cnt[sz]=;root[rt]=sz;return;}
    int now=root[rt],f=;
    while (now)
        {
            if (key[now]==v) {cnt[now]++;update(now);update(f);splay(rt,now,);break;}
            f=now; now=son[now][key[now]<v];
            if (now==)
                {
                    sz++;son[sz][]=son[sz][]=;key[sz]=v;size[sz]=;
                    cnt[sz]=;fa[sz]=f;son[f][key[f]<v]=sz;
                    update(f);splay(rt,sz,);break;
                }
        }
}
int find(int rt,int x)
{
    int now=root[rt];
    while (now)
    {
        if (key[now]==x) return now;
        if (key[now]>x) now=son[now][];
        else now=son[now][];
    }
}
int findrank(int rt,int x)
{
    int now=root[rt],ans=;
    while (now)
    {
        if (key[now]>x) now=son[now][];
        else if (key[now]<x)
            ans+=(cnt[now]+size[son[now][]]),now=son[now][];
        else {ans+=size[son[now][]];break;}
    }
    return ans;
}
int findkth(int rt,int x)
{
    int now=root[rt];
    while (now)
        {
            if (son[now][] && x<=size[son[now][]]) now=son[now][]; else
                {
                    int temp;
                    if (son[now][]) temp=size[son[now][]]+cnt[now];
                        else temp=cnt[now];
                    if (x<=temp) return key[now];
                    x-=temp; now=son[now][];
                }
        }
}
int prev(int rt)
{
    int now=son[root[rt]][];
    while (son[now][]) now=son[now][];
    return now;
}
bool remove(int rt,int now)
{
    int fi=find(rt,now);
    if (fi==-) return false;
    else splay(rt,fi,);
    if (cnt[root[rt]]>) {cnt[root[rt]]--; size[root[rt]]--; return true;};
    if (!son[root[rt]][] && !son[root[rt]][]) {clear(root[rt]); root[rt]=; return true;}
    if (!son[root[rt]][])
        {int oldroot=root[rt]; root[rt]=son[root[rt]][]; fa[root[rt]]=; clear(oldroot); return true;}
    else if (!son[root[rt]][])
            {int oldroot=root[rt]; root[rt]=son[root[rt]][]; fa[root[rt]]=; clear(oldroot); return true;}
    int leftbig=prev(rt),oldroot=root[rt];
    splay(rt,leftbig,);
    fa[son[oldroot][]]=root[rt]; son[root[rt]][]=son[oldroot][];
    clear(oldroot); update(root[rt]); return true;
}
int Prev(int rt,int x)
{
    int now=root[rt],ans=-0x7fffffff;
    while (now)
        {
            if (key[now]<x)
                {if (ans<key[now])ans=key[now]; now=son[now][];}
            else now=son[now][];
        }
    return ans;
}
int Succ(int rt,int x)
{
    int now=root[rt],ans=0x7fffffff;
    while (now)
        {
            if (key[now]>x)
                {if (ans>key[now]) ans=key[now]; now=son[now][];}
            else now=son[now][];
        }
    return ans;
}
//SegmentTree---------------------------------------------------------------------------------------
void buildTree(int now,int l,int r)
{
    for (int i=l; i<=r; i++) insert(now,a[i]);
    if (l==r) return;
    int mid=(l+r)>>;
    buildTree(now<<,l,mid); buildTree(now<<|,mid+,r);
}
int FindRank(int now,int l,int r,int L,int R,int rk)
{
    if (L<=l && R>=r) return findrank(now,rk);
    int mid=(l+r)>>,rak=;
    if (L<=mid) rak+=FindRank(now<<,l,mid,L,R,rk);
    if (mid<R) rak+=FindRank(now<<|,mid+,r,L,R,rk);
    return rak;
}
int FindKth(int L,int R,int kt)
{
    int ll=,rr=maxx,mid;
    while (ll<rr)
        {
            mid=(ll+rr)>>;
            if (FindRank(,,n,L,R,mid)<kt) ll=mid+;
                else rr=mid;
        }
    return ll-;
}
void ChangeK(int now,int l,int r,int p,int k)
{
    remove(now,a[p]); insert(now,k);
    if (l==r) {a[p]=k;return;}
    int mid=(l+r)>>;
    if (p<=mid) ChangeK(now<<,l,mid,p,k);
    else ChangeK(now<<|,mid+,r,p,k);
}
int GetPrev(int now,int l,int r,int L,int R,int k)
{
    int mid=(l+r)>>,pre=-0x7fffffff;
    if (L<=l && R>=r) return Prev(now,k);
    if (L<=mid) pre=max(pre,GetPrev(now<<,l,mid,L,R,k));
    if (mid<R) pre=max(pre,GetPrev(now<<|,mid+,r,L,R,k));
    return pre;
}
int GetSucc(int now,int l,int r,int L,int R,int k)
{
    int mid=(l+r)>>,suc=0x7fffffff;
    if (L<=l && R>=r) return Succ(now,k);
    if (L<=mid) suc=min(suc,GetSucc(now<<,l,mid,L,R,k));
    if (mid<R) suc=min(suc,GetSucc(now<<|,mid+,r,L,R,k));
    return suc;
}
//Solve---------------------------------------------------------------------------------------------
void solve_1(int l,int r,int k) {printf("%d\n",FindRank(,,n,l,r,k)+);}
void solve_2(int l,int r,int k) {printf("%d\n",FindKth(l,r,k));}
void solve_3(int pos,int k) {ChangeK(,,n,pos,k);}
void solve_4(int l,int r,int k) {printf("%d\n",GetPrev(,,n,l,r,k));}
void solve_5(int l,int r,int k) {printf("%d\n",GetSucc(,,n,l,r,k));}
//void debug(int now)
//{
//    if (!now) return;
//    debug(son[now][0]);
//    printf("%d-%d个 ",key[now],cnt[now]);
//    debug(son[now][1]);
//}
//main----------------------------------------------------------------------------------------------
int main()
{
//    freopen("output.out","w",stdout);
    n=read(),m=read();
    for (int i=; i<=n; i++) a[i]=read(),maxx=max(maxx,a[i]);
    buildTree(,,n);
    for (int i=; i<=m; i++)
        {
            int opt=read(),l,r,k,pos;
            switch (opt)
                {
                    case : l=read(); r=read(); k=read(); solve_1(l,r,k); break;
                    case : l=read(); r=read(); k=read(); solve_2(l,r,k); break;
                    case : pos=read(); k=read(); solve_3(pos,k); break;
                    case : l=read(); r=read(); k=read(); solve_4(l,r,k); break;
                    case : l=read(); r=read(); k=read(); solve_5(l,r,k); break;
                }    //for (int i=1;i<=17;i++) debug(root[i]),puts("");
        }

    return ;
}

让南爷看了两个shabi错误...[好友'智商'已经掉线]...秀了一波智商下限TAT''

UPD:ShallWe大爷的 权值线段树套区间线段树  没调..留着以后学姿势

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 51000
using namespace std;
int tn,Hash[N],a[N],head[N];
int n,m,totp,totin,rt;
struct P{
    int l,r,in;
} p[];
struct I{
    int l,r,sz;
} in[];
struct Q{
    int type,l,r,k;
} query[N];

inline int read()
{    char ch=getchar();int flag=;for(;ch<''||ch>'';ch=getchar())if(ch=='-') flag=-;
    int x=; for(;ch>=''&&ch<='';x=x*+ch-,ch=getchar());return x*flag;
}
inline int DC(int x)
{    return lower_bound(Hash+,Hash++tn,x)-Hash;}

inline int DCC(int x)
{    int w=lower_bound(Hash+,Hash++tn,x)-Hash;
     return w-; 

}

inline int DCCC(int x)
{    int w=upper_bound(Hash+,Hash++tn,x)-Hash;}

inline void  Up(int x)
{    in[x].sz=in[in[x].l].sz+in[in[x].r].sz;}

void Insert(int &x,int l,int r,int w,int delta)
{    if (!x) x=++totin;
//    cout<<x<<endl;
//    cout<<l<<' '<<r<<' '<<w<<endl;
    if (l==r){
        in[x].sz+=delta;
        return;
    }    int mid=(l+r)>>;
    if (w<=mid) Insert(in[x].l,l,mid,w,delta);
    else Insert(in[x].r,mid+,r,w,delta);
    Up(x);
}

void Add(int &x,int l,int r,int val,int whe,int delta)
{    if (!x) x=++totp;
//    cout<<l<<' '<<r<<' '<<val<<' '<<whe<<endl;
    Insert(p[x].in,,n,whe,delta);
    if (l==r) return; int mid=(l+r)>>;
    if (val<=mid) Add(p[x].l,l,mid,val,whe,delta);
    else    Add(p[x].r,mid+,r,val,whe,delta);
}

int Get_sz_in(int x,int l,int r,int L,int R)
{    if (!x) return ;
    if (L>R) return x;
    if (L<=l&&r<=R) return in[x].sz;
    int mid=(l+r)>>,now=;
    if (L<=mid)     now+=Get_sz_in(in[x].l,l,mid,L,R);
    if (R>mid) now+=Get_sz_in(in[x].r,mid+,r,L,R);
    return now;
}

int Get_sz(int x,int l,int r,int L,int R,int il,int ir)
{    if (!x) return ;
    if (L>R) return ;
//    cout<<x<<' '<<l<<' '<<r<<' '<<endl;
    if (L<=l&&r<=R) return Get_sz_in(p[x].in,,n,il,ir);
    int mid=(l+r)>>,now=;
    if (L<=mid) now+=Get_sz(p[x].l,l,mid,L,R,il,ir);
    if (R>mid) now+=Get_sz(p[x].r,mid+,r,L,R,il,ir);
    return now;
}

inline int Find_rate(int l,int r,int k)
{    int sz=Get_sz(rt,,tn,,k-,l,r);
    return sz+;
}

inline int Find_kth(int l,int r,int k)
{    int L=,R=tn,x=rt;
    while (L<R)
    {    int mid=(L+R)>>;
        int Left=Get_sz_in(p[p[x].l].in,,n,l,r);
        if (Left>=k) R=mid,x=p[x].l;
        if (Left<k) k-=Left,L=mid+,x=p[x].r;
    }
    return Hash[L];
}
int main()
{    freopen("a.in","r",stdin);
    n=read(),m=read();
    for (int i=;i<=n;i++)
        Hash[i]=a[i]=read();
    tn=n;
    int x,y,z,type ;
    for (int i=;i<=m;i++)
    {    type=query[i].type=read();
        if (type==)
        {    query[i].l=read();
            query[i].k=read();
            Hash[++tn]=query[i].k;
        }else{
            query[i].l=read();
            query[i].r=read();
            query[i].k=read();
        }
    }
//    for (int i=1;i<=m;i++)
//    cout<<query[i].l<<' '<<query[i].r<<' '<<query[i].k<<endl;
    sort(Hash+,Hash++tn);
    tn=unique(Hash+,Hash++tn)-Hash;
    for (int i=;i<=n;i++)
        Add(rt,,tn,a[i]=DC(a[i]),i,+);
//    for(int i=1;i<=n;i++) cout<<a[i]<<endl;
    for (int i=;i<=m;i++)
    {    int l=query[i].l,r=query[i].r,k=query[i].k;
//        cout<<query[i].type<<endl;
        switch (query[i].type){
            case :{
                printf("%d\n",Find_rate(l,r,DC(k)));
                break;
            }
            case :{
                printf("%d\n",Find_kth(l,r,k));
                break;
            }
            case :{
                Add(rt,,tn,a[l],l,-);
                Add(rt,,tn,a[l]=DC(k),l,);
                break;
            }
            case :{
                int now=DCC(k);
                int x=Get_sz(rt,,tn,l,r,now,now);
                if (x)
                    printf("%d\n",Hash[now]);
                else
                    printf("%d\n",Find_kth(l,r,Find_rate(l,r,now)-));
                break;
            }
            case :{
                int now=DCCC(k);
                int x=Get_sz(rt,,tn,l,r,now,now);
                if (x)
                    printf("%d\n",Hash[now]);
                else
                    printf("%d\n",Find_kth(l,r,Find_rate(l,r,now)));
                break;
            }
        }
    }
    return ;
}

ShallWe's Code