模拟赛搬了这题，场切了顺手写个题解。
这种题当然先考虑单组询问怎么做，然后再拓展出去。
设按位与的集合是 \(A\)，按位或的集合是 \(B\)，结果都是 \(x\)，我们考虑 \(A,B\) 的元素应该满足的性质。不难发现，所有 \(y<x\) 的 \(y\) 都应该在 \(B\)，\(y>x\) 的 \(y\) 都应该在 \(A\)。反证法不难发现。直接暴力枚举单组都会寄掉。
考虑把这个东西拓展到 popcount 上。定义 \(p(x)\) 为 \(x\) 在二进制下 \(1\) 的个数。我们考虑什么数应该被分进 \(A\)，什么数应该被分进 \(B\)。设 \(\textrm{AND } A_i=\textrm{OR }b_i=k\)。而找答案的时候，我们可以暴力枚举 \(p(k)\) 的值。这是直接枚举 \(k\) 所不能做到的。
令 \(x=p(k)\)。显然 \(x\le p(y),y\in A\)，\(x\ge p(z),z\in B\)。所以对于一个数 \(y\)，如果满足 \(p(y)>x\) 就应该被分入 \(A\)，满足 \(p(y)<x\) 就应该被分入 \(B\)。考虑 \(p(y)=x\) 的情况。容易发现这样的 \(y\) 应该都相等，反证易知。设 \(A\) 中此时的元素的 \(\textrm{AND}\) 为 \(A_1\)，\(B\) 中此时的元素的 \(\textrm{OR}\) 为 \(B_1\)。设使得 \(p(y)=x\) 的 \(y\) 有 \(d\) 个。设此时的 \(p(y)=x\) 都为 \(T\)，判是否合法有以下三种：
- \(d=0\)：不考虑：因为这样的情况可以被其他的 \(x\) 情况所描述。
- \(d\ge1\)：判断是否有 \(A_1 \textrm{ or }T=B_1\)。
- \(d\ge 2\)：判断是否有 \(A_1\textrm{ or }T=B_1\textrm{ and }T\)。
这样可以做描述所有合法情况。容易写出来一个 \(O(\log V)\) 判断合法性的东西。具体可以这样写：
对于一个集合 \(S\)，考虑维护所有
popcount为 \(x\) 的数的按位与，按位或的值，以及数量。查询时直接考虑对这堆信息做前后缀维护，枚举断点 \(k\) 根据上面提到的分类判断。判断的复杂度可以做到 \(O(\log V)\)。
考虑怎么拓展到多组询问上，有两种做法。
做法一，考场做法：
可以考虑根号分治。离线所有询问。对于 \(r-l+1\leq \sqrt n\) 的询问直接暴力求。对于 \(r-l+1>\sqrt n\) 的，可以按照左端点分块。把所有询问发配到左端点的块上。
对于同一个块中的所有询问，按照右端点 \(r\) 排序。具体就是，设 \(l\) 所在块右端点为 \(l_1\)，那么这种询问的 \([l,r]=[l,l_1]+[l_1+1,r]\)。\([l,l_1]\) 暴力求，但是 \([l_1+1,r]\) 一起求。总复杂度 \(O(n\sqrt n\log V)\)，可以通过本题。
做法二，std 做法：
可以考虑分治，设当前分治到区间 \([l,r]\)，中点为 \(mid=\lfloor\dfrac{l+r}{2}\rfloor\)。单次分治我们只需要处理 \(L\in [l,mid],R\in (mid,r]\) 的所有询问。
我们对右半部分进行前缀信息维护，对右半部分进行前缀信息维护。具体就是，枚举相等的值的 popcount。维护前缀或，前缀与，后缀或，后缀与，以及前后缀相等的。然后一个询问区间可以通过合并左半边后缀以及右半边前缀得到。按照那三条判断合法性的方法直接判断即可。
总时间复杂度 \(O(n\log n\log V)\)，可以通过本题。
做法一参考代码：
#include<bits/stdc++.h>
#define pb push_back
#define F(i,a,b) for(int i=a;i<=(b);i++)
#define dF(i,a,b) for(int i=a;i>=(b);i--)
#define lowbit(x) (x&(-x))
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
const int mod=998244353,maxn=114514;
int n,m,a[maxn];
int popcount(int x){
int rt=0;
for(;x;x^=lowbit(x)) rt++;
return rt;
}
bool ans[maxn];
struct node{
struct CCF{
int asum=-1,osum=0,cnt=0;
};
vector<CCF>tmp;
node():tmp(31){}
void insert(int x){
const int y=popcount(x);
tmp[y].cnt++;
tmp[y].osum|=x;
tmp[y].asum&=x;
}
bool query(){
vector<int>suf(32);
suf[31]=-1;
dF(i,30,0) suf[i]=suf[i+1]&tmp[i].asum;
int cur=0;
F(i,0,30){
cur|=tmp[i].osum;
int num=tmp[i].cnt;
if((cur==suf[i+1]&&num)||(num>=2&&cur==suf[i])) return 1;
}
return 0;
}
};
vector<tuple<int,int,int>>q[maxn];
signed main(){
n=read(),m=read();
F(i,1,n) a[i]=read();
int len=sqrt(n);
F(i,1,m){
int l=read(),r=read();
if(r-l<=len){
node cur;
F(j,l,r) cur.insert(a[j]);
ans[i]=cur.query();
}
else q[(l-1)/len].pb(make_tuple(r,l,i));
}
F(i,0,n/len) if(!q[i].empty()){
sort(q[i].begin(),q[i].end());
int p=(i+1)*len+1;
node cur;
for(auto [r,l,id]:q[i]){
for(;p<=r;++p) cur.insert(a[p]);
node tmp=cur;
dF(j,(i+1)*len,l) tmp.insert(a[j]);
ans[id]=tmp.query();
}
}
F(i,1,m) puts(ans[i]?"YES":"NO");
}