题解 | 牛客练习赛105F

不会猫树qwq

提供一个分块思路吧。设块大小为$BB$，记$m=1024m\; =\; 1024$

观察到复杂度要偏向预处理，考虑维护区间$FWTFWT$点积，询问时再$IFWTIFWT$。

块内直接每个区间求出来，$O({\displaystyle \frac{n}{B}}{B}^2)=O(nBm)O(\backslash dfrac\; nB\; B^2)\; =\; O(nBm)$

并求出所有$S(L,R)S(L,R)$表示第$LL$个块到第$RR$个块的$FWTFWT$点积，$O(({\displaystyle \frac{n}{B}}{)}^{2}m)O((\backslash dfrac\; nB)^2m)$

查询就直接问出两端散块中间整块拿来乘，或者有可能直接在一块内询问，都是$O(m)O(m)$

最后利用$FWT(FWT(a){)}_i=m\cdot a_{i}FWT(FWT(a))\_i\; =\; m\; \backslash cdot\; a\_i$单点求值，$O(m)O(m)$

$B=\sqrt[3]{n}B\; =\; \backslash sqrt[3]\{n\}$时平衡，时间复杂度为$O(nm\log m+n\sqrt[3]{n}m+qm)O(nm\; \backslash log\; m\; +\; n\backslash sqrt[3]\{n\}m\; +\; qm)$

赛时代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=54551060