题目描述
维护一个集合,支持如下几种操作:
1. “I x”,插入一个数x;
2.“Q x”,询问数x是否在集合中出现过;
现在要进行N次操作,对于每个询问操作输出对应的结果。
样例
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
解题思路:
用c++STL库map即可。数据范围小,$1≤N≤10^5$,$O(nlogn)$算法能过。
虽然map的原理与数组不同,但是可以当数组用哦。
C++代码:(复杂度:$O(nlogn)$)
#include<bits/stdc++.h>//万能头文件
using namespace std;
#define re register
#define Re register
int n;
map<int,bool>_map;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);//奇技淫巧
cin >> n;
while(n--){
char ch;
int tmp;
cin >> ch >> tmp;
if(ch == 'I'){
_map[tmp] = true;//赋值
}
else {//判断
if(_map[tmp])cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}