2016年icpc大连现场赛补题

1/4

HDU 5972 字符串匹配

shift-and算法。设bitset数组B[ch]存储字符ch在模式串的位置，设bitset D存储匹配结果。如果D[n-1]=1，n为模式串长度，则匹配成功。维护D：D=D<<1&B[ch]，ch为输入的字符。

HDU 5975
树状数组原理+想法题
当添加一个数字(x)时，会将区间([x−lowbit(x)+1, x])内的数字添加进一个新的集合，代价是区间数字个数。给一个(n≤10^{18})和(Q≤10^5)次询问。

*1 L R 添加区间 ([L,R]) 的所有数字的代价和
*2 x询问(x)被添加进新的集合的次数(当添加([1,n])所有数字时)
对每次询问输出答案。

思路：对于操作一可以用区间减法，对于单个(x)，花费了(lowbit(x))，然后就是求([1,R])的所有(lowbit)和-([1,L-1])的所有的(lowbit)和
我们可以枚举二进位即(2^i)进行统计
对于操作二就是每次加(x&-x),然后统计加了多少次
代码