CF2143F

询问中位置

i

能取到的数是

a_{l\sim i}

中选数异或能得到的数。显然我们可以对每个左端点求出合法的最大

r

。此时有一个暴力，从前往后，设位置

i-1

操作后变成

a'_{i-1}

，在

a_{l\sim i}

的线性基中找到能表出的第一个大于

a'_{i-1}

的数。

考虑固定左端点后，右端点线性基的变化次数是

O(\log V)

的，可以一次处理一整段。求线性基变化点可以倒着枚举

l

，将

l

加入变化点，然后枚举变化点加入线性基，删除未变化的点。根据线性基的性质，不会有非变化点变为变化点。

枚举每一段，设上一个数是

a'

，在这一段的线性基里查能表出的

>a'

的数的个数。若小于这一段的长度，更新

r

并退出。否则在线性基里查一次第

k

大更新

a'

。能表出的

>a'

的数的个数和第

k

大都容易从高往低贪心计算。具体方式是分类讨论一下，枚举组合出的值与这个数的 LCP，如果在某一位比较出来了，线性基中比这一位低的数可以随便选。

O(n\log^2V)

。

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[200005],r[200005];
template<typename T,int maxn>struct basis{
  T b[maxn];
  int cnt;
  basis(){
    memset(b,0,sizeof(b)),cnt=0;
  }
  bool insert(T k){
    if(cnt==maxn)return 0;
    for(int i=maxn-1;i>=0;i--){
      if(k>>i&1){
        if(!b[i])return b[i]=k,cnt++,1;
        k^=b[i]; 
      }
    }
    return 0;
  }
  T query(int k,T ans=0){
    if(k>=1<<maxn)return 1<<cnt;
    for(int i=maxn-1,now=0,num=cnt;i>=0;i--){
      if(b[i])num--;
      if(k>>i&1){
        if(~now>>i&1){
          ans+=1<<num;
          if(b[i])now^=b[i];
          else return ans;
        }
        else if(b[i])ans+=1<<num;
      }
      else{
        if(now>>i&1){
          if(b[i])now^=b[i];
          else return ans;
        }
      }
    }
    return ans;
  }
  T kth(int k){
    T now=0;
    for(int i=maxn-1,num=cnt;i>=0;i--){
      if(!b[i])continue;
      num--;
      if(k<=1<<num){
        if(now>>i&1)now^=b[i];
      }
      else{
        k-=1<<num;
        if(~now>>i&1)now^=b[i];
      }
    }
    return now;
  }
};
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>t;
  while(t--){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int>p(1,n+1);
    for(int i=n;i>=1;i--){
      vector<int>nxt(1,i);
      basis<int,20>b;
      b.insert(a[i]);
      for(int j=0;j<p.size()-1;j++)if(b.insert(a[p[j]]))nxt.push_back(p[j]);
      nxt.push_back(n+1),p=nxt,b=basis<int,20>(),b.insert(a[i]);
      for(int j=1,v=0;j<p.size();j++){
        int num=b.query(v);
        if((1<<b.cnt)-num<p[j]-p[j-1]){
          r[i]=p[j-1]+(1<<b.cnt)-num-1;
          break;
        }
        else r[i]=p[j]-1,v=b.kth(num+p[j]-p[j-1])+1;
        b.insert(a[p[j]]);
      }
    }
    for(int i=1,x,y;i<=m;i++)cin>>x>>y,puts(r[x]>=y?"Yes":"No");
  }
  return 0;
}

文章操作

相关推荐

评论

CF2143F