题目大意：
给你一个序列
{
a
}
\{a\}
{a},每次询问一个区间
[
l
,
r
]
[l,r]
[l,r]
问你这个区间里面的数是否可以分成两部分使得一部分的
A
N
D
=
AND=
AND=另一部分的
O
R
OR
OR
解题思路：
- 这个题思路很妙：
- 首先我们知道对于 & \& &操作数越多只会越 & \& &越小，而 ∣ | ∣就是相反的
- 那么我们可以假设这个区间里面的数可以分成两部分，那么假设最后的答案是 a n s ans ans
- 假设 a n s ans ans中有 x x x个1,那么对于区间里面数包含的1的个数大过 x x x的话那么一定是执行 & \& &操作，反过来同理小的就是 ∣ | ∣操作。
- 但是如果是刚好为 x x x怎么办？，它是 & \& &还是 ∣ | ∣呢？
- 这里还要再讨论一下：
- 如果刚好为 x x x的数是不同的？那么它们一定是要划分到一个集合里面（如果它们在不同的集合里面肯定结果不会相等）
- 如果 x x x的数都是一样的那么我们就可以划分到两边，也可以在一边,分成两边的时候你最起码个数要大于1
那么思路就很明显了：我们枚举 x ∈ [ 0 , 30 ] x\in[0,30] x∈[0,30],然后 [ 0 , x − 1 ] [0,x-1] [0,x−1]里面的数求 ∣ | ∣, [ x + 1 , 30 ] [x+1,30] [x+1,30]里面的数取 & \& &,那么对于 x x x我们要记录里面的数是否是同一个数。和数的个数
那么我们就可以开 30 30 30棵线段树。每个维护区间里面1个数为 x x x的各种信息。
AC code
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 800010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
struct inf {
int a, b, c;
}all;
struct Segtree {
int OR[maxn];
int AND[maxn];
int is[maxn];// 区间里面的数是否是一种而已？
int sum[maxn];//区间数额个数
inline void pushup(int rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
if(!is[rt<<1]) is[rt] = is[rt<<1|1];
else if(!is[rt<<1|1]) is[rt] = is[rt<<1];
else if(is[rt<<1|1] != is[rt<<1]) is[rt] = -1;
else is[rt] = is[rt<<1];
OR[rt] = (OR[rt<<1] | OR[rt<<1|1]);
AND[rt] = (AND[rt<<1] & AND[rt<<1|1]);
}
void build(int rt, int l, int r) {
if(l == r) {
OR[rt] = sum[rt] = is[rt] = 0;
AND[rt] = (1<<30)-1;
return;
}
build(Lson);
build(Rson);
pushup(rt);
}
void insert(int rt, int l, int r, int pos, int val) {
if(l == r) {
sum[rt] = 1;
is[rt] = OR[rt] = AND[rt] = val;
return;
}
if(pos <= mid) insert(Lson,pos,val);
else insert(Rson,pos,val);
pushup(rt);
}
inline inf mege(inf a, inf b) {
inf res;
res.a = a.a & b.a;
res.b = a.b | b.b;
res.c = a.c + b.c;
return res;
}
inf quaryAND_OR_SUM(int rt, int l, int r, int L, int R) {
if(L <= l && R >= r) return (inf){AND[rt],OR[rt],sum[rt]};
inf res = {(1<<31)-1,0,0};
if(L <= mid) res = mege(quaryAND_OR_SUM(Lson,L,R),res);
if(R > mid) res = mege(quaryAND_OR_SUM(Rson,L,R),res);
return res;
}
int quaryis(int rt, int l, int r, int L, int R) {
if(L <= l && R >= r) return is[rt];
if(L > mid) return quaryis(Rson,L,R);
else if(R <= mid) return quaryis(Lson,L,R);
else {
int lson = quaryis(Lson,L,R);
int rson = quaryis(Rson,L,R);
if(lson == -1 || rson == -1) return -1;
if(!lson) return rson;
if(!rson) return lson;
if(lson == rson) return lson;
return -1;
}
}
}sgt[40];
// n个点，q个询问，Less[i]是[0,i]里面所有数的OR,eq[i]是x=i时候的数的AND和OR
int n, q, AND[40], OR[40], arr[maxn], Less[40], more;
bool eqis[40], isOR[40], flag, isAND;
PII eq[40];
int main() {
read(n,q);
for(int i = 0; i <= 30; ++ i) sgt[i].build(1,1,n); //建线段树
for(int i = 1; i <= n; ++ i) {
read(arr[i]);
int num = 0;
for(int j = 30; j >= 0; j --) {// 获取每个数的1的个数
if(arr[i] >> j & 1)
num ++;
}
sgt[num].insert(1,1,n,i,arr[i]); // 插到对应位置去
}
while(q --) {
int l, r;
read(l,r);
for(register int i = 0; i <= 30; ++ i) {// 枚举x
inf is = sgt[i].quaryAND_OR_SUM(1,1,n,l,r);// 获取[l,r]区间里面的AND OR sum
AND[i] = is.a;
OR[i] = is.b;
eqis[i] = is.c; // x=i是否存在
isOR[i] = is.c; //是否OR过了也就是[0,i]是否有数
if(i) isOR[i] |= isOR[i-1];
(i != 0) ? (Less[i] = Less[i-1] | OR[i]) : (Less[i] = OR[i]); //维护前缀OR
if(!is.c) continue;//如果下面没数了
int _is = sgt[i].quaryis(1,1,n,l,r);
eq[i] = {AND[i],OR[i]};//x = i时候数的 AND 和 OR
if(is.c >= 2 && _is != -1) eq[i].first = -2;// 这里设置-2是为了判断那个x全是同一个数并且个数>= 2
}
flag = 0, isAND = 0; // flag是答案，isAND就是判断是否AND过了
more = (1<<31)-1;
for(register int i = 30; i >= 1 && !flag; -- i) {//枚举&的位置i-2, i-1 和 i
more &= AND[i];
isAND |= eqis[i];
if(i == 1) break;
if(!eqis[i-1]) { // 如果没有x=i-1看[0,i-2]和[i,30]是否相等
if(more == Less[i-2] && isAND && isOR[i-2]) flag = 1;
continue;
}
if(eq[i-1].first == -2) {
if((Less[i-2]|eq[i-1].second) == (more&eq[i-1].second)) flag = 1;
eq[i-1].first = eq[i-1].second; // 记得复原eq[i-1].first
}
if(isAND && (Less[i-2] | eq[i-1].second) == more) flag = 1;
if(isOR[i-2] && (more & eq[i-1].first) == Less[i-2]) flag = 1;//分到AND和OR集合
}
if(eqis[30]) {//特判两个边界
if(eq[30].first == -2) {
eq[30].first = eq[30].second;
if((Less[29]|eq[30].second) == eq[30].second) flag = 1;
}
if(isOR[29] && Less[29] == eq[30].first) flag = 1;
}
if(eqis[0]) {
if(eq[0].first == -2) {
if((more&eq[0].second) == eq[0].second) flag = 1;
}
if(isAND && more == eq[0].second) flag = 1;
}
puts(flag ? "YES" : "NO");
}
return 0;
}
/*
5 1
1 1 1 1 1
1 2
7 1
4 2 9 6 2 4 2
5 6
4 1
4 4 3 0
2 3
*/