本题其实可以用STL做的
使用map存储每一个字符串即可
C++代码 时间复杂度：$O(nlogn)$
#include<bits/stdc++.h>
using namespace std;
#define re register
#define Re register
#define ll long long
#define MAXN 100005
int n;
char ch;
string s;
map<string,int>_map;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for(Re int i = 1;i <= n;i++){
cin >> ch;
cin >> s;//虽然map本质原理与数组不同，但其实可以当数组用滴
if(ch == 'I')
_map[s]++;
else cout << _map[s] << endl;
}
return 0;
}
不错，我翻题解就是为了找找有没有人和我一样用的map
哈哈，我也是
hahhahhaha 太可爱了 人家本来就是练习前缀树而出的题目 ，我想截屏给灿神看
时间复杂度为啥是nlogn不是就循环了一次吗
就循环了一次，但是map其实是平衡树啊，你所看到的
_map[s]++cout << _map[s] << endl;都是$O(logn)$复杂度的~~~~再乘上那一重循环就是nlogn了
trie的时间复杂度是多少啊
Trie 的字符串搜索时间复杂度为 O (m) ，m 为最长的字符串的长度，其查询性能与集合中的字符串的数量无关
这里register的使用是可以忽略的， 一般不需要用到这个 ， 某些情况下把变量保存在寄存器中反而会降低程序的运行速度。因为被占用的寄存器不能再用于其它目的；或者变量被使用的次数不够多，不足以装入和存储变量所带来的额外开销。
确实太厉害了hh~~~
在NOIP系列比赛中register一般起不到明显的作用。
蒟蒻我就是开register习惯了。。。
啊这....对于大的数据来说，这样做的方法可能不太好？
用
unordered_map做，照样可以过~（用法与map相似）unordered_map太费空间了。。。