zcmimi's blog

arrow_back莫队共13篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

S_i表示[1,i]的异或和,区间[l,r]的异或和就是S_r \bigoplus S_{l-1}

那么题目可以转化为[l-1,r]中有多少对S_i \bigoplus S_j = k,直接用莫队统计就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

cnt数组记录每种数字出现的次数

我们只需要考虑add(x),del(x),其他的交给莫队

我们考虑当前数原本的答案是a_x \times cnt_x^2

现在变成a_x \times (cnt_x+1)^2

cnt_x =y

(y+1)^2 = y^2 + 2y +1

所以更新的时候ans += a_x \times (cnt_x \times 2 + 1)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

D-query top: 0

就是莫队的板子题

2/2
Search
search