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

题目大意：

经黄学长指出，此题原题出自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行，每行一个整数，代表当前全集中小于或等于当前新生成集合的数量

样例输入

样例输出

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=;RG int c=Blue();RG bool b=false;

    for(;c<||c>;c=Blue())

        if(c==)b=true;

    for(;c>&&c<;c=Blue())

        x=(x<<)+(x<<)+c-;

    if(b)x=-x;

}

int n,ans;

struct Treap{

#define L long long

    struct Nt{

        Nt *ch[],*s1,*s2;

        int size,k;

        L v;

        inline void pud() {size=ch[]->size+ch[]->size+;}

    }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()*+rand(); p->v=mid; p->size=;

            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[]->size+,insert(o->ch[],p,o->v+,r)):(insert(o->ch[],p,l,o->v-));

        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[],l,o->v-);

        Relabel(o->ch[],o->v+,r);

    }

public:

    void init(){

        root=null=pool+n+;

        null->ch[]=null->ch[]=null;

        pool->v=;

        (pool+n+)->v=inf+;

    }

    inline void insert(RG int cnt,RG int u,RG int v){

        ans=;

        pool[cnt].s1=pool+u;

        pool[cnt].s2=pool+v;

        pool[cnt].ch[]=pool[cnt].ch[]=null;

        Re_p=null;

        insert(root,pool+cnt,,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=,u,v;i<=n;i++){

        Rin(u),Rin(v);

        RT.insert(i,u,v);

    }

    close_file();

    return ;

}

FJoi2017 1月21日模拟赛 comparison(平衡树+thita重构)的相关教程结束。