【SEERC 2020 H】AND = OR 题解

题目大意

  定义一个序列是好的，当且仅当能把这个序列里的数划分成两个非空集合，使得一个集合的 and 等于另一个集合的 or。
  给定 $a_1,\cdots,a_n$，有 $q$ 个询问，每次询问 $a_l,\cdots,a_r$ 是否是好的。

  $n,q \le 10^5,\ 0 \le a_i < 2^{30}$
  3s

$$\\$$ $$\\$$ $$\\$$

题解

  and 会把数字越 and 越小，or 会把数字越 or 越大，所以应该让“大”的数去 and，“小”的数去 or。
  怎么定义“大”和“小”呢？如果就按数值来分，是可以的，可以证明如果询问一个区间 $[l,r]$，一定是把这个区间从小到大排序后从某个位置切开，小的部分 or，大的部分 and，但似乎不太能做这题。。。
  另一种“大”和“小”的定义是二进制下 1 的个数。对于每个询问，假设最终答案有 $x$ 个 1，那么比 $x$ 多的 $a_i$ 就应当 and，比 $x$ 小的 $a_i$ 就应当 or。而恰好有 $x$ 个 1 的 $a_i$，要么全都扔向同一边，要么它们全都相等（都等于答案）然后分到两边。
  所以对于每个询问，用主席树求出这个区间以 1 的数量为下标的前缀 or 以及后缀 and，然后枚举 $x$ 判断即可。注意如果要把恰好有 $x$ 个 1 的 $a_i$ 扔到两边的话，那么这样的 $a_i$ 的数量要 $\ge 2$。因此主席树要记录区间 or、区间 and、区间元素数量。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int maxn=1e5+5, MX=30, maxtot=2e6+5;

struct AST{
	int val,num,i;
};
bool cmpA(const AST &a,const AST &b) {return a.num<b.num;}

int n,q;
AST a[maxn];

int totOr,totAnd,tr_or[maxtot],tr_and[maxtot],tr_cnt[maxtot],son_or[maxtot][2],son_and[maxtot][2];
int rootOr[MX+2],rootAnd[MX+2],resOr,resAnd,resCnt;
void tr_xg_or(int k,int last,int l,int r,int x,int z) {
	while (l<r) {
		tr_or[k]=tr_or[last]|z;
		tr_cnt[k]=tr_cnt[last]+1;
		int mid=(l+r)>>1;
		if (x<=mid) {
			son_or[k][1]=son_or[last][1];
			son_or[k][0]=++totOr;
			k=totOr, last=son_or[last][0], r=mid;
		} else {
			son_or[k][0]=son_or[last][0];
			son_or[k][1]=++totOr;
			k=totOr, last=son_or[last][1], l=mid+1;
		}
	}
	tr_or[k]=tr_or[last]|z;
	tr_cnt[k]=tr_cnt[last]+1;
}
void tr_xg_and(int k,int last,int l,int r,int x,int z) {
	while (l<r) {
		tr_and[k]=tr_and[last]&z;
		int mid=(l+r)>>1;
		if (x<=mid) {
			son_and[k][1]=son_and[last][1];
			son_and[k][0]=++totAnd;
			k=totAnd, last=son_and[last][0], r=mid;
		} else {
			son_and[k][0]=son_and[last][0];
			son_and[k][1]=++totAnd;
			k=totAnd, last=son_and[last][1], l=mid+1;
		}
	}
	tr_and[k]=tr_and[last]&z;
}
void tr_cx(int kOr,int lastOr,int kAnd,int l,int r,int x,int y) {
	if (x<=l && r<=y) {
		resOr|=tr_or[kOr];
		resAnd&=tr_and[kAnd];
		resCnt+=tr_cnt[kOr]-tr_cnt[lastOr];
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) tr_cx(son_or[kOr][0],son_or[lastOr][0],son_and[kAnd][0],l,mid,x,y);
	if (mid<y) tr_cx(son_or[kOr][1],son_or[lastOr][1],son_and[kAnd][1],mid+1,r,x,y);
}

int sumOr[MX+5],sumAnd[MX+5],cnt[MX+5];
int main() {
	scanf("%d %d",&n,&q);
	fo(i,1,n) {
		scanf("%d",&a[i].val);
		a[i].num=__builtin_popcount(a[i].val);
		a[i].i=i;
	}
	sort(a+1,a+1+n,cmpA);
	
	int i=1;
	fo(w,0,MX) {
		if (w) rootOr[w]=rootOr[w-1];
		for(; i<=n && a[i].num==w; i++) {
			int last=rootOr[w];
			tr_xg_or(rootOr[w]=++totOr,last,1,n,a[i].i,a[i].val);
		}
	}
	tr_and[0]=(1<<30)-1;
	i=n;
	fd(w,MX,0) {
		rootAnd[w]=rootAnd[w+1];
		for(; i && a[i].num==w; i--) {
			int last=rootAnd[w];
			tr_xg_and(rootAnd[w]=++totAnd,last,1,n,a[i].i,a[i].val);
		}
	}
	
	while (q--) {
		int l,r;
		scanf("%d %d",&l,&r);
		
		int sumCnt=0;
		fo(w,0,MX) {
			resOr=0, resAnd=(1<<30)-1, resCnt=0;
			tr_cx(rootOr[w],(w==0 ?0 :rootOr[w-1]),rootAnd[w],1,n,l,r);
			sumOr[w]=resOr;
			sumAnd[w]=resAnd;
			cnt[w]=resCnt;
			sumCnt+=resCnt;
		}
		
		bool ans=0;
		int numLess=0;
		fo(w,0,MX) {
			if (numLess && numLess<sumCnt && sumOr[w-1]==sumAnd[w]) {ans=1; break;}
			if (sumOr[w]==sumAnd[w] && cnt[w]>=2) {ans=1; break;}
			numLess+=cnt[w];
		}
		
		puts(ans ?"YES" :"NO");
	}
}