CF1100F Ivan and Burgers

链接

有点像 P1972 [SDOI2009]HH的项链？

将区间按 (r) 排序，对于在线性基中的每个元素，其在序列中的位置肯定是尽量靠右，所以插入时如果插入值与线性基在某一位上都为 (1)，则比较其在序列中的位置，若插入值靠右则交换，继续插入。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pi pair<int,int>
#define mk make_pair
#define pb push_back
using namespace std;
const int N=5e5+3,M=21;
int n,m,val[N],ans[N];
vector<pi>a[N];
IL int in(){
  char c;int f=1;
  while((c=getchar())<'0'||c>'9')
    if(c=='-') f=-1;
  int x=c-'0';
  while((c=getchar())>='0'&&c<='9')
    x=x*10+c-'0';
  return x*f;
}
struct Base{
  int bas[M],pos[M];
  IL void ins(int x,int t){
	  for(int i=20;~i;--i)
	    if(x>>i&1){
			  if(!bas[i]){bas[i]=x,pos[i]=t;return;}
			  else if(pos[i]<t) swap(bas[i],x),swap(pos[i],t);
				x^=bas[i];
			}
	}
	IL int ask(int x,int t){
	  for(int i=20;~i;--i)
	    if((x^bas[i])>x&&pos[i]>=t) x^=bas[i];
	  return x;
	}
}A;
int main()
{
	int x,y;
	n=in();
	for(int i=1;i<=n;++i) val[i]=in();
	m=in();
	for(int i=1;i<=m;++i)
	  x=in(),y=in(),a[y].pb(mk(x,i));
	for(int i=1;i<=n;++i){
		A.ins(val[i],i);
	  for(int j=0;j<a[i].size();++j)
	    ans[a[i][j].second]=A.ask(0,a[i][j].first);
	}
	for(int i=1;i<=m;++i) printf("%d
",ans[i]);
  return 0;
}