题目分析

直接使用拉链法，h[k]可以看做映射到k的元素构成链表的表头
注意：h[N]要初始化为-1

相关代码

//拉链法
//h[k]可以看做映射到k的元素构成链表的表头
//h[N]要初始化为-1
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
const int mod=100003;

int h[N];
int e[N];
int ne[N];
int idx=0;

void insert(int x){
    int k=(x%mod+mod)%mod;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx;
    idx++;
}

bool query(int x){
    int k=(x%mod+mod)%mod;
    for(int i=h[k];i!=-1;i=ne[i]){
        if(e[i]==x)
            return true;
    }
    return false;
}

int main(){
    int n;
    cin>>n;
    memset(h,-1,sizeof(h));
    for(int i=0;i<n;i++){
        string str;
        int x;
        cin>>str>>x;
        if(str=="I"){
            insert(x);
        }

        if(str=="Q"){
            if(query(x)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}