1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
| #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"); } }
|