表单（数据修复版）
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
本题为牛客小白月赛15C-表单数据修复版本。
子弹上膛的声音，是我唱歌的先兆。
——百里守约-朱雀志
小T有一张一共有n nn个字符串的字符串表，因为小T TT是神所以他可以任意修改这张表，
因为小T TT是个强迫症，所以他想方设法的使这些字符不同，所以现在他进行以下操作Q QQ次：
- 操作一：给字符串表中加入一个字符串s ss。
- 操作二：给字符串表去重，输出去掉字符串的数量。
请输出每次操作二的结果。
输入描述：
第一行输入两个整数n , Q ( 1 ≤ n , Q ≤ 5 × 10 5 ) n,Q(1≤n,Q≤5×10^5)n,Q(1≤n,Q≤5×105)，表示字符串表中字符串的数量、操作次数。
此后n nn行，第i ii行输入一个长度为l e n g t h ( t i ) length(t_i)length(ti)，仅由小写字母组成的字符串t i ( 1 ≤ l e n g t h ( t i ) ≤ 40 ) t_i(1≤length(t_i)≤40)ti(1≤length(ti)≤40)，表示初始字符串表中的一个字符串。
此后Q QQ行，第i ii行先输入一个数字o i ( 1 ≤ o i ≤ 2 ) o_i(1≤o_i≤2)oi(1≤oi≤2)，表示第i ii个字符串的操作类型，操作编号对应题干。若o i = 1 o_i=1oi=1，在同一行额外输入一个长度为l e n g t h ( s i ) length(s_i)length(si)，仅由小写字母组成的字符串s i ( 1 ≤ l e n g t h ( s i ) ≤ 40 ) s_i(1≤length(s_i)≤40)si(1≤length(si)≤40)，表示要加入的字符串。
输出描述：
对于每一个操作二，新起一行输出一个整数，表示去掉的字符串数量。
示例1
输入：
4 4 play the pubg game 1 game 1 pubg 2 2输出：
2 0解题思路
本题是哈希集合去重 + 重复计数维护的模拟题，通过哈希结构快速判断字符串是否已存在，仅用一个变量维护重复总数，即可高效处理大规模的添加与去重操作。
核心原理
去重操作的本质是保留每个字符串的唯一副本，移除所有多余的重复项，因此单次去重移除的字符串数量 = 当前字符串总数 - 不同字符串的数量。
由于去重后表中不再存在重复字符串，无需维护完整的字符串计数，仅需一个变量记录累积的重复个数即可。
算法流程
- 数据结构选择：使用哈希表（或哈希集合）存储所有已出现过的不同字符串，保证平均O(1)时间复杂度的存在性查询。
- 初始化处理：逐个读入初始的n个字符串：
- 若字符串已在哈希表中，重复计数加1。
- 若未出现过，将其加入哈希表。
- 处理Q次操作：
- 操作1（添加字符串）：判断字符串是否已存在。存在则重复计数+1；不存在则加入哈希表。
- 操作2（去重）：输出当前的重复计数，随后将重复计数置为0（去重后无多余重复项）。
复杂度分析
- 时间复杂度：平均O(n + Q)，每次字符串的查询与插入均为平均O(1)，总操作量为初始n个加Q次操作，适配5×10^5的数据规模。
- 空间复杂度：O(S)，S为所有不同字符串的总字符长度，存储所有唯一字符串。
总结
核心逻辑：利用哈希结构快速判重，维护一个变量记录累积的重复字符串数，去重操作直接输出重复数并清零，无需遍历全表统计。
关键操作：哈希存在性判断、重复计数增量更新、去重后计数清零。
效率保障：平均常数级单步操作，配合输入输出加速，可轻松处理十万级数据量。
代码简要说明
- 哈希表与计数变量：
unordered_map<string, bool>记录字符串是否存在，变量r维护当前重复字符串的总数。 - 初始数据处理：循环读入n个初始字符串，逐个判重，重复则
r自增，否则存入哈希表。 - 操作循环：
- 读取操作类型，若为操作1，读入字符串后判重，更新重复计数或哈希表。
- 若为操作2，输出当前重复数
r，并将r置0，模拟去重后无重复的状态。
- 输入输出优化：关闭C++流同步、解绑cin与cout，输出使用
'\n'替代endl，避免频繁刷新缓冲区，大幅提升大数量级下的读写速度。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,q;cin>>n>>q;unordered_map<string,bool>h;ll r=0;for(ll i=0;i<n;i++){string s;cin>>s;if(h.count(s))r++;elseh[s]=1;}for(ll i=0;i<q;i++){ll op;cin>>op;if(op==1){string s;cin>>s;if(h.count(s))r++;elseh[s]=1;}else{cout<<r<<'\n';r=0;}}return0;}
