首页 > 代码库 > FJoi2017 1月21日模拟赛 comparison(平衡树+thita重构)

FJoi2017 1月21日模拟赛 comparison(平衡树+thita重构)

2024-09-01 23:34:37   219人阅读

题目大意：

经黄学长指出，此题原题出自2014湖北省队互测 没有人的算术

规定集合由二元组(A,B)构成，A、B同时也是两个这样的集合，即A、B本身也是二元组

规定二元组S为严格最小集合，S=（S，S），规定T为严格最大集合T=（T，T）

刚开始我们有两个集合S和T，即全局最小集合和全局最大集合，编号分别为0，n+1

下面我们规定集合的比较规则，是递归定义的

我们称集合X(X1,X2)等于Y(Y1,Y2)当且仅当

X1=Y1 并且 X2=Y2

我们称集合X(X1,X2)小于Y(Y1,Y2)当且仅当

1.X1<Y1

2.X1==Y1 且 X2<Y2

现在有n个操作：

1.将集合u、v合并为新二元组集合X(u,v)

2.输出所有小于或等于X的集合数量

输入

第一行一个整数n，代表有n个操作

下面n行，每行2个数u、v代表将集合u、v组合成新的集合

输出

共n行，每行一个整数，代表当前全集中小于或等于当前新生成集合的数量

样例输入

3031 00 310 13 33 44 23 431 32 25 39 48 19 1213 513 1213 03 124 315 1816 1611 514 179 2020 1816 1031 2420 77 514 2124 4

样例输出

222456697910111112131279171714191322192723122327

Solution

orz神犇wwx

法一：

先考虑最暴力的做法，那就是O(n*n)的递归比较

得分10

法二：

考虑将集合维护成一个有序序列，用插入排序O(n)解决一个点的插入，就可以O(1)得出答案，比较就是比数组下标就行了哦

得分30

法三：

显然可以用平衡树维护大小关系嘛，把原来数组变成一个映射，将下标映射到区间[0,oo)上记为Val，其中S取0，T去oo，插入时，若集合X大小在A、B间，则Val(X)=(Val(A)+Val(B))/2

那么，每次插入后为了维护Val，就要重构遍平衡树

得分100

下面是标解

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>#define MaxN 50010#define MaxBuf 1<<22#define inf LONG_LONG_MAX/2#define mid ((l>>1)+(r>>1)+(l&r&1))#define RG register#define inline __inline__ __attribute__((always_inline))#define Blue() ((S==T&&(T=(S=B)+fread(B,1,MaxBuf,stdin),S==T))?0:*S++)char B[MaxBuf],*S=B,*T=B;template<class Type>inline void Rin(RG Type &x){    x=0;RG int c=Blue();RG bool b=false;    for(;c<48||c>57;c=Blue())        if(c==45)b=true;    for(;c>47&&c<58;c=Blue())        x=(x<<1)+(x<<3)+c-48;    if(b)x=-x;}int n,ans;struct Treap{#define L long long    struct Nt{        Nt *ch[2],*s1,*s2;        int size,k;        L v;        inline void pud() {size=ch[0]->size+ch[1]->size+1;}    }pool[MaxN],*null,*root,*Re_p;    L Re_s,Re_t;    inline void rotate(RG Nt *&o,RG bool d){        RG Nt *k=o->ch[d];        o->ch[d]=k->ch[!d];        k->ch[!d]=o;        o->pud();        k->pud();        o=k;    }    void insert(RG Nt *&o,RG Nt *p,RG L l,RG L r){        if(o==null){                o=p;            p->k=rand()*2333+rand(); p->v=mid; p->size=1;            printf("%d\n",ans);            return;        }        RG bool d=(p->s1->v > o->s1->v) || (p->s1->v == o->s1->v && p->s2->v >= o->s2->v);        d? (ans+=o->ch[0]->size+1,insert(o->ch[1],p,o->v+1,r)):(insert(o->ch[0],p,l,o->v-1));        if(o->ch[d]->k < o->k)rotate(o,d),Re_p=o,Re_s=l,Re_t=r;        o->pud();    }    void Relabel(Nt *o,L l,L r){        if(o==null)return;        o->v=mid;        Relabel(o->ch[0],l,o->v-1);        Relabel(o->ch[1],o->v+1,r);    }public:    void init(){        root=null=pool+n+2;        null->ch[0]=null->ch[1]=null;        pool->v=0;        (pool+n+1)->v=inf+1;    }    inline void insert(RG int cnt,RG int u,RG int v){        ans=2;        pool[cnt].s1=pool+u;        pool[cnt].s2=pool+v;        pool[cnt].ch[0]=pool[cnt].ch[1]=null;        Re_p=null;        insert(root,pool+cnt,1,inf);        Relabel(Re_p,Re_s,Re_t);    }}RT;#define set_file(File) {freopen(#File".in","r",stdin); freopen(#File".out","w",stdout);}#define close_file() {fclose(stdin); fclose(stdout);}int main(){    srand(‘K‘+‘a‘+‘i‘+‘b‘+‘a‘);    set_file(comparison);    Rin(n); RT.init();    for(RG int i=1,u,v;i<=n;i++){        Rin(u),Rin(v);        RT.insert(i,u,v);    }    close_file();    return 0;}

 

FJoi2017 1月21日模拟赛 comparison(平衡树+thita重构)


联系
我们