【COGS 1534】 [NEERC 2004]K小数 &&【COGS 930】 [河南省队2012] 找第k小的数 可持久化01Trie

板子题，只是记得负数加fix最方便

#include <cstdio>

const int A=,N=;

namespace FIFO

{

    char ch,B[<<],*S=B,*T=B;

    #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)

    #define isd(c) (c>='0'&&c<='9')

    int aa,bb;int F(){

        while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=:(aa=ch-'',bb=);

        while(ch=getc(),isd(ch))aa=aa*+ch-'';return bb?aa:-aa;

    }

}

#define gi FIFO::F()

struct Trie{

    Trie *ch[];int size;

}*root[N],*null,node[(<<)+];

int n,m,sz=;

int main(){

    freopen("kth.in","r",stdin);freopen("kth.out","w",stdout);

    null=node,null->ch[]=null->ch[]=null,root[]=null;

    n=gi,m=gi;for(register int i=,x;i<=n;i++){

        root[i]=node+sz,sz++,x=gi;register Trie *p=root[i],*last=root[i-];

        for(register int i=A;i>=;i--)

            p->ch[(x>>i)&]=node+sz,sz++,p->ch[((x>>i)&)^]=last->ch[((x>>i)&)^],

            p=p->ch[(x>>i)&],last=last->ch[(x>>i)&],p->size=last->size+;

    }

    register int x,y,k;while(m--){

        x=gi,y=gi,k=gi;register Trie *a=root[x-],*b=root[y];register int ret=;

        for(register int i=A;i>=;i--)

            if(b->ch[]->size-a->ch[]->size>=k)a=a->ch[],b=b->ch[];

            else ret|=(<<i),k-=b->ch[]->size-a->ch[]->size,a=a->ch[],b=b->ch[];

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

    }

}

【COGS 930】 [河南省队2012] 找第k小的数

#include <cstdio>

const int A=,N=,fox=;

namespace FIFO

{

    char ch,B[<<],*S=B,*T=B;

    #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)

    #define isd(c) (c>='0'&&c<='9')

    int aa,bb;int F(){

        while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=:(aa=ch-'',bb=);

        while(ch=getc(),isd(ch))aa=aa*+ch-'';return bb?aa:-aa;

    }

}

#define gi FIFO::F()

struct Trie{

    Trie *ch[];int size;

}*root[N],*null,node[(<<)+];

int n,m,sz=;

int main(){

    freopen("kthnumber.in","r",stdin);freopen("kthnumber.out","w",stdout);

    null=node,null->ch[]=null->ch[]=null,root[]=null;

    n=gi,m=gi;for(register int i=,x;i<=n;i++){

        root[i]=node+sz,sz++,x=gi+fox;register Trie *p=root[i],*last=root[i-];

        for(register int i=A;i>=;i--)

            p->ch[(x>>i)&]=node+sz,sz++,p->ch[((x>>i)&)^]=last->ch[((x>>i)&)^],

            p=p->ch[(x>>i)&],last=last->ch[(x>>i)&],p->size=last->size+;

    }

    register int x,y,k;while(m--){

        x=gi,y=gi,k=gi;register Trie *a=root[x-],*b=root[y];register int ret=;

        for(register int i=A;i>=;i--)

            if(b->ch[]->size-a->ch[]->size>=k)a=a->ch[],b=b->ch[];

            else ret|=(<<i),k-=b->ch[]->size-a->ch[]->size,a=a->ch[],b=b->ch[];

        printf("%d\n",ret-fox);

    }

}

【COGS 1534】 [NEERC 2004]K小数