【codevs 1230】元素查找 splay……

高级数据结构——bool数组！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
const int MAXM = 100000 + 5;
bool hash[MAXN];
int n,m,k;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&k);
        if(k <= 100000)
            hash[k] = true;
    }
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d",&k);
        puts(hash[k] ? "YES" : "NO");
    }
    return 0;
}

好吧标题党了
其实我打的是二叉搜索树（二分查找树？）
普通的二叉搜索树哦~~

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
using namespace std;
const int MAXN = 100000 + 5;
int sz;
struct treedot
{
    int left,right,num;
    void clear()
    {
        this -> left = 0;
        this -> right = 0;
        this -> num = 0;
        return;
    }
}t[MAXN];
bool find(int x)
{
    int e = 1;
    while(true)
    {
        if(t[e].num == x)
            return true;
        if(t[e].num < x)
        {
            if(!t[e].left)
                return false;
            e = t[e].left;
        } 
        else
        {
            if(!t[e].right)
                return false;
            e = t[e].right;
        }
    }
    return true;
}
void insert(int x)
{
    int e = 1;
    while(true)
    {
        if(t[e].num == x)
        {
            //puts("呵呵呵");
            return;
        }
        if(t[e].num < x)
        {
            if(!t[e].left)
            {
                t[e].left = ++ sz;
                t[sz].clear();
                t[sz].num = x;
                return;
            }
            e = t[e].left;
        }
        else
        {
            if(!t[e].right)
            {
                t[e].right = ++ sz;
                t[sz].clear();
                t[sz].num = x;
                return;
            }
            e = t[e].right;
        }
    }
    return;
}
void del(int x)
{
    int e = 1,fa = 0;
    while(true)
    {
        if(t[e].num == x)//delete
        {
            if(!t[e].left)
            {
                if(t[fa].num > x)
                {
                    t[fa].right = t[e].right;
                    t[e].clear();
                    return;
                }
                else
                {
                    t[fa].left = t[e].right;
                    t[e].clear();
                    return;
                }
            }
            else if(!t[t[e].left].right)
            {
                if(t[fa].num > x)
                {
                    t[fa].right = t[e].left;
                    t[e].clear();
                    return;
                }
                else
                {
                    t[fa].left = t[e].left;
                    t[e].clear();
                    return;
                }
            }
            else
            {
                int d = e;
                while(t[t[d].right].right)
                {
                    d = t[d].right;
                }
                if(t[fa].num > x)
                {
                    t[fa].right = t[d].right;
                }
                else
                {
                    t[fa].left = t[d].right;
                }
                int h = t[d].right;
                t[h].right = t[e].right;
                t[h].left = t[e].left;
                t[e].clear();
                return;
            }

        }
        fa = e;
        if(t[e].num < x)
        {
            if(!t[e].left)
            {
                puts("Fuck You!!!");
                return;
            }
            e = t[e].left;
        } 
        else
        {
            if(!t[e].right)
            {
                puts("Fuck You!!!");
                return;
            }
            e = t[e].right;
        }
    }
    return;
}
void clear()
{
    memset(t,0,sizeof(struct treedot)*MAXN);
}
string s;
int z;
char hehe[MAXN];
int n,m;
int x;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&x);
        insert(x);
    }
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d",&x);
        if(find(x))
            puts("YES");
        else
            puts("NO");
    }
}