P7470 [NOI Online 2021 提高组] 岛屿探险 乱糊的做法
-
定义
x_{(k)} 为x 从高位到低位数的第k 位的位值，x_{((k))} 为x 从高位到低位数截取前k 位的数。 -
显然
a\le b 等价于\sum_{k=1}^{24}([[a_{((k-1))}=b_{((k-1))}]\& [a_{(k)}=0]\&[b_{(k)}=1]])+[a=b] -
于是我们便可以拆位算贡献。
-
类比此题的那个形式，酷似该模型，但是我们发现
\min(b,d) 很烦人，考虑去掉这个限制。 -
将每个询问按
d 从小到大排序，每次d 变大时，[b_i\le d] 就有些会发生改变，可以证明一共发生改变的次数仅为O(n) 级别。 -
考虑维护一个数据结构完成此问题，先枚举
k ，然后做些预处理，会发现其实我们可以分讨一下b_i\le d 的情况，定义t_i=[b_i\le Now_d] 。 -
令
c_i={a_i}_{((k-1))},d_i={b_i}_{((k-1))}, e_i={a_i}_{(k)},g_i={b_i}_{(k)},F={Now_c}_{((k-1))},F_c={Now_c}_{(k)},H={Now_d}_{((k-1))},H_c={Now_d}_{(k)} 。 -
当
t_i=1 时，F=c_i\oplus d_i,e_i\oplus F_c=0,g_i=1,t_i=1 ，对于每个i 建一个多元组为\{c_i\oplus d_i,e_i,g_i,t_i\} ，即询问某个区间内有多少个多元组等于\{F,F_c,1,1\} ，这可以使用Range Count Query套路解决。 -
否则
t_i=0 时，c_i\oplus F=H,e_i\oplus F_c=0,H_c=1,t_i=0 ，对于每个i 建一个多元组为\{c_i,e_i,0,t_i\} ，即询问某个区间内有多少个多元组等于\{F\oplus H,F_c,1,0\} ，这也可以使用Range Count Query套路解决。 -
然后做完了。