二进制分组
维护难以合并的信息,支持以下操作
1、加入一个信息
2、强制在线,查询全局信息
举个例子:String Set Queries
1、往集合中加一个字符串
2、从集合中删除一个字符串
3、给一个字符串
强制在线,即得到上一个问题的答案才能知道下一次的真正操作。
插入和查询
先假设没有操作
查询
考虑一个基于暴力重构的方法:
(前面铺垫过很多次,这次就不提根号了)
将新插入的字符串构建一个新的
如果相邻两个
什么情况呢,就是比如现在已经有了几个
现在新加入一个字符串,变成了
发现最后两个
递归下去得到
容易证明任意时刻最多有
当查询时,在
时间复杂度:每个字符串最多只被合并进新
每次查询最多只有
删除
删除需要信息满足可减性,如题目中的统计次数。
建立一个新的二进制分组,把所有删除的字符串放在新的二进制分组里。
依旧统计出现的字符串,在答案中减去这部分。
如果是求最值等不可减的信息,就不能用这个方法了。