yaohaoyou

题目传送器

更爽的阅读体验

前言

赛时想出的做法，结果过了一周才过，非常难写，常数还大，本文其实可以认为是做法的补充，只用到了一个性质。

做法

先分析一些性质。

1. 对于询问的区间 $[l,r]$，将区间排序后，显然结果是一个前缀 $a_1,a_2...a_k$ 的或和等于后缀 $a_{k+1},a_{k+2}...a_n$ 的与和，因为或和的最小值为 $a_k$，与和的最大值为 $a_{k+1}$，$a_k\le a_{k+1}$，所以两个部分一定可以不交，即形成一个前缀和后缀。
2. 设与和 $=$ 或和 $=x$。按位考虑，若 $x$ 的第 $i$ 位为 $0$，则分界点 $k$ 满足 $[l,k]$ 的第 $i$ 位都是 $0$，且 $[k+1,r]$ 中至少有一个 $0$。若 $x$ 的第 $i$ 位为 $1$，则 $k$ 满足 $[k+1,r]$ 的第 $i$ 位都是 $1$，$[l,k]$ 至少有一个 $1$。

第二条性质本质上就是说明，若第 $i$ 位为 $0$，设第 $i$ 位的一个极长前缀 $[1,L]$ 满足 2，则 $k\in[1,L]$，若第 $i$ 为为 $1$，设第 $i$ 位的一个极长后缀 $[R+1,n]$ 满足 2，则 $k\in[R+1,n]$。

具体实现就是建一棵主席树，在主席树上二分得到满足以上要求的极长前缀和后缀，则最终的分界点 $k$ 必然满足在每一位都在 $[1,L_i]$ 或 $[R_i+1,n]$ 区间中，即若满足 $\exist k,k\in[1,L_i]\cup[R_i+1,n]$，则答案为YES，否则为NO。本质上就是对每个区间求交集。

分析时间复杂度，对每一位做主席树上二分为 $\mathcal{O}((q+n)\times \log_2V\times \log_2n)$，求交集可以将每个区间先取反，再求并集是否为全集即可 $\mathcal{O}(q\times \log_2V\times \log_2\log_2V)$。

具体实现时，可以将询问离线，对每个位先求出 $q$ 个询问的极长前后缀，最后求交集，这样可以将空间复杂度将为 $\mathcal{O}(n\times\log_2n)$，时间常数减小，再添加一些小剪枝就通过了。

Code