p1110 报表统计（FHQ-TREAP/TREAP）

平衡树的裸题，操作都相当简单

写了一个FHQ，但是奈何常数太大，实在过不去

最后写了一个Treap开O2水过

TREAP代码

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <ctime>

using namespace std;

struct node{

    int sz,key,ran,l,r,re;

}tr[500100<<2];

int maxsize=0,ans=0,root1=0,root2=0,fir[500100],back[500100],min3=0x3f3f3f3f;

void update(int k){

    tr[k].sz=tr[tr[k].l].sz+tr[tr[k].r].sz+tr[k].re;

}

void roratel(int &o){

    int k=tr[o].r;

    tr[o].r=tr[k].l;

    tr[k].l=o;

    tr[k].sz=tr[o].sz;

    update(o);

    o=k;

}

void rorater(int &k){

    int o=tr[k].l;

    tr[k].l=tr[o].r;

    tr[o].r=k;

    tr[o].sz=tr[k].sz;

    update(k);

    k=o;

}

void insert(int &k,int x){

    if(k==0){

        ++maxsize;

        k=maxsize;

        tr[k].sz=1;

        tr[k].re=1;

        tr[k].key=x;

        tr[k].ran=rand();

        return;

        }

    tr[k].sz++;

    if(tr[k].key==x){

        tr[k].re++;

    }

    else{

        if(x>tr[k].key){

            insert(tr[k].r,x);

            if(tr[tr[k].r].ran<tr[k].ran)

                roratel(k);}

        else{

            insert(tr[k].l,x);

            if(tr[tr[k].l].ran<tr[k].ran)

                rorater(k);}

    }

}

void del(int &k,int x){

    if(k==0)

        return;

    if(tr[k].key==x){

        if(tr[k].re>1){

            tr[k].re--;

            tr[k].sz--;

            return;

        }

        if(tr[k].l*tr[k].r==0){

            k=tr[k].l+tr[k].r;

            return;

        }

        else{

            if(tr[tr[k].l].ran<tr[tr[k].r].ran){

                rorater(k);

                del(k,x);

                }

            else{

                roratel(k);

                del(k,x);

            }

        }

    }

    else{

        if(x>tr[k].key){

            tr[k].sz--;

            del(tr[k].r,x);

            }

        else{

            tr[k].sz--;

            del(tr[k].l,x);

            }

    }

}

int rank1(int k,int x){

    if(k==0)

        return 0;

    if(tr[k].key==x){

        return tr[tr[k].l].sz+1;

    }

    else{

        if(x>tr[k].key)

            return rank1(tr[k].r,x)+tr[k].re+tr[tr[k].l].sz;

        else

            return rank1(tr[k].l,x);

    }

}

int rank2(int k,int x){

    if(k==0)

        return 0;

    if(x<=tr[tr[k].l].sz){

        return rank2(tr[k].l,x);

    }

    else if(x>(tr[tr[k].l].sz+tr[k].re))

        return rank2(tr[k].r,x-tr[tr[k].l].sz-tr[k].re);

    else

        return tr[k].key;

}

void pre(int k,int x){

    if(k==0)

        return;

    if(tr[k].key<x){

        ans=k;

        pre(tr[k].r,x);

    }

    else if(tr[k].key==x&&tr[k].re>1){

        ans=k;

        return;

    }

    else

        pre(tr[k].l,x);

}

void beh(int k,int x){

    if(k==0)

        return;

    if(tr[k].key>x){

        ans=k;

        beh(tr[k].l,x);

    }

    else if(tr[k].key==x&&tr[k].re>1){

        ans=k;

        return;

    }

    else

        beh(tr[k].r,x);

}

//root1 - 2 root2 - 3

int main(){

    // freopen("9.in","r",stdin);

    // freopen("test.out","w",stdout);

    srand(19260817);

    int n,m;

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)

        scanf("%d",&back[i]),fir[i]=back[i];

    for(int i=1;i<=n-1;i++){

        insert(root1,abs(back[i]-back[i+1]));

        insert(root2,back[i]);

    }

    // printf("%d %d\n",root1,root2);

    insert(root2,back[n]);

    insert(root2,0x3f3f3f3f);

    insert(root2,-0x3f3f3f3f);

    for(int i=1;i<=n;i++){

        // printf("pre=%d beh=%d val=%d\n",pre(back[i],root2),beh(back[i],root2),back[i]);

        beh(root2,back[i]);

        int behans=tr[ans].key;

        pre(root2,back[i]);

        int preans=tr[ans].key;

        min3=min(min3,min(abs(behans-back[i]),abs(preans-back[i])));

    }

    char opt[20];

    for(int i=1;i<=m;i++){

        scanf("%s",opt);

        if(opt[0]=='I'){

            int poi,addx;

            scanf("%d %d",&poi,&addx);

            insert(root2,addx);

            beh(root2,addx);

            int behans=tr[ans].key;

            pre(root2,addx);

            int preans=tr[ans].key;

            min3=min(min3,min(abs(behans-addx),abs(preans-addx)));

            del(root1,abs(fir[poi+1]-back[poi]));

            insert(root1,abs(fir[poi+1]-addx));

            insert(root1,abs(addx-back[poi]));

            back[poi]=addx;

        }

        else{

            if(opt[4]=='G'){

                printf("%d\n",rank2(root1,1));

            }

            else

                printf("%d\n",min3);

        }

    }

    return 0;

}

FHQ-TREAP代码

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

struct Node{

    int sz,w,ran,lson,rson;

}FHQ[501000<<2];

int Nodecnt,back[501000],root1,root2,min3=0x3f3f3f3f,fir[501000];

int newNode(int w){

    ++Nodecnt;

    FHQ[Nodecnt].sz=1;

    FHQ[Nodecnt].w=w;

    FHQ[Nodecnt].ran=rand();

    FHQ[Nodecnt].lson=FHQ[Nodecnt].rson=0;

    return Nodecnt;

}

void pushup(int o){

    FHQ[o].sz=FHQ[FHQ[o].lson].sz+FHQ[FHQ[o].rson].sz+1;

}

void split_val(int now,int k,int &x,int &y){

    if(!now){

        x=y=0;

        return;

    }

    if(FHQ[now].w<=k){

        x=now;

        split_val(FHQ[now].rson,k,FHQ[now].rson,y);

    }

    else{

        y=now;

        split_val(FHQ[now].lson,k,x,FHQ[now].lson);

    }

    pushup(now);

}

int merge(int x,int y){//X.W < Y.W

    if(!x||!y)

        return x+y;

    pushup(x);

    pushup(y);

    if(FHQ[x].ran<FHQ[y].ran){

        FHQ[x].rson=merge(FHQ[x].rson,y);

        pushup(x);

        return x;

    }

    else{

        FHQ[y].lson=merge(x,FHQ[y].lson);

        pushup(y);

        return y;

    }

}

void insert(int x,int &root){

    int mergeroot=newNode(x),a,b;

    split_val(root,x,a,b);

    root=merge(merge(a,mergeroot),b);

}

void erase(int x,int &root){

    int a,b,c,d;

    split_val(root,x,a,b);

    split_val(a,x-1,c,d);

    root=merge(merge(c,merge(FHQ[d].lson,FHQ[d].rson)),b);

}

int findkth(int now,int kth){

    if(now==0)

        return 0;

    if(kth==FHQ[FHQ[now].lson].sz+1)

        return now;

    if(kth<=FHQ[FHQ[now].lson].sz)

        return findkth(FHQ[now].lson,kth);

    else

        return findkth(FHQ[now].rson,kth-FHQ[FHQ[now].lson].sz-1);

}

int findrank(int &now,int wx){

    int a,b;

    split_val(now,wx-1,a,b);

    int ans = FHQ[a].sz+1;

    now=merge(a,b);

    return ans;

}

int pre(int x,int &root){

    int a,b;

    split_val(root,x,a,b);

    int ans=FHQ[findkth(a,FHQ[a].sz-1)].w;

    root=merge(a,b);

    return ans;

}

int beh(int x,int &root){

    int a,b;

    split_val(root,x-1,a,b);

    int ans=FHQ[findkth(b,2)].w;

    root=merge(a,b);

    return ans;

}

//root1 - 2 root2 - 3

int main(){

    // freopen("9.in","r",stdin);

    // freopen("test.out","w",stdout);

    srand(19260817);

    int n,m;

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)

        scanf("%d",&back[i]),fir[i]=back[i];

    for(int i=1;i<=n-1;i++){

        insert(abs(back[i]-back[i+1]),root1);

        insert(back[i],root2);

    }

    // printf("%d %d\n",root1,root2);

    insert(back[n],root2);

    insert(0x3f3f3f3f,root2);

    insert(-0x3f3f3f3f,root2);

    for(int i=1;i<=n;i++){

        // printf("pre=%d beh=%d val=%d\n",pre(back[i],root2),beh(back[i],root2),back[i]);

        min3=min(min3,min(abs(beh(back[i],root2)-back[i]),abs(pre(back[i],root2)-back[i])));

    }

    char opt[20];

    for(int i=1;i<=m;i++){

        scanf("%s",opt);

        if(opt[0]=='I'){

            int poi,addx;

            scanf("%d %d",&poi,&addx);

            insert(addx,root2);

            min3=min(min3,min(abs(beh(addx,root2)-addx),abs(pre(addx,root2)-addx)));

            erase(abs(fir[poi+1]-back[poi]),root1);

            insert(abs(fir[poi+1]-addx),root1);

            insert(abs(addx-back[poi]),root1);

            back[poi]=addx;

        }

        else{

            if(opt[4]=='G')

                printf("%d\n",FHQ[findkth(root1,1)].w);

            else

                printf("%d\n",min3);

        }

    }

    return 0;

}

巴特西

p1110 报表统计（FHQ-TREAP/TREAP）

最新文章

热门文章