首页 > 代码库 > AC日记——平衡树练习 codevs 4244

AC日记——平衡树练习 codevs 4244

4244 平衡树练习

 

思路:

  有节操的人不用set也不用map;

 

代码:

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 5000005int n,m,ch[maxn][2],key[maxn],root;inline void in(int &now){    int if_z=1;now=0;    char Cget=getchar();    while(Cget>9||Cget<0)    {        if(Cget==-) if_z=-1;        Cget=getchar();    }    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }    now*=if_z;}inline int tree_build(int l,int r){    int now=l+r>>1;    if(now>l) ch[now][0]=tree_build(l,now-1);    if(now<r) ch[now][1]=tree_build(now+1,r);    return now;}inline bool find(int x){    int now=root;    while(1)    {        if(x==key[now]) return true;        if(x<key[now]) now=ch[now][0];        else now=ch[now][1];        if(!now) return false;    }}int main(){    in(n),in(m);int pos;    for(int i=1;i<=n;i++) in(key[i]);    sort(key+1,key+n+1);    n=unique(key+1,key+n+1)-key-1;    root=tree_build(1,n);    for(;m--;) in(pos),printf("%d ",find(pos));    return 0;}

 

AC日记——平衡树练习 codevs 4244