一个小题目

这应该是某道题的弱化版。

题目就是给定一个正整数序列,长度 \leqslant 3 \times 10^5 ,然后值域是到 [1,10^9]

q 个询问 (q \leqslant 3 \times 10^5) ,每次呢给定一个数字 w (值域还是 [1,10^9] ),和区间 [l,r]

然后你可以把 w 异或上序列的 [l,r] 内的任意数字任意次。

要求最后的 w' 最小。

 

那么我们先来思考一个简单点的问题。如果是给定整个序列,那么我们可以预处理出序列的线性基

然后可以做到 O(\log_2 10^9) 内回答一个询问。

具体做法就是从高到低地,如果这一位非零,那就异或这一位的线性基然后继续下一位。

 

那么下面我们说一下线性基合并。线性基合并就是把其中一个线性基暴力地插入另一个线性基。

这样做的复杂度是 O(\log_2^2 10^9) 的。

那么我们可以用线段树/ST表等任意 \log 区间数据结构去维护线性基合并。

建议用ST表,这样预处理尽管带了三个 \log ,但是回答却是两个 \log 的,而且比线段树常数小。

 

可是有什么方法把整个算法也从三个变为两个 \log 呢?

分治!把回答离线,先递归处理掉左右两侧的回答,再处理跨中线的回答就好了。

每次返回的时候都合并一下。

 

那么还有一个相关的问题,和这种无关的。

把刚刚的问题修改一下,我们只能选择区间内的任意数字然后异或一次。

oh!可持久化Trie!

每次递归地往下走就好了。

非常好写。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据