表单（数据修复版）【牛客tracker 每日一题】

表单数据修复版时间限制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_i1oi​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_mapstring, bool记录字符串是否存在变量r维护当前重复字符串的总数。初始数据处理循环读入n个初始字符串逐个判重重复则r自增否则存入哈希表。操作循环读取操作类型若为操作1读入字符串后判重更新重复计数或哈希表。若为操作2输出当前重复数r并将r置0模拟去重后无重复的状态。输入输出优化关闭C流同步、解绑cin与cout输出使用\n替代endl避免频繁刷新缓冲区大幅提升大数量级下的读写速度。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,q;cinnq;unordered_mapstring,boolh;ll r0;for(ll i0;in;i){string s;cins;if(h.count(s))r;elseh[s]1;}for(ll i0;iq;i){ll op;cinop;if(op1){string s;cins;if(h.count(s))r;elseh[s]1;}else{coutr\n;r0;}}return0;}