解析

做幸運數字的時候逛題解區爬過來的
挺妙的

把所有詢問離線下來，按右端點排序
貪心的讓最高位更高的向量出現的盡可能向右
實現上可以把線性基里的向量和當前的數swap來實現
代碼就非常好寫了

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define inf (n+1) //#define debug(...) fprintf(stderr,__VA_ARGS__) const int N=5e5+100; const int M=2e5+10500; const double eps=1e-5; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m;struct node{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; }ll mi[65];int v[35],pos[35]; void upd(int x,int id){for(int i=20;i>=0;i--){if(x&(1<<i)){if(!v[i]){v[i]=x;pos[i]=id;break;} if(pos[i]<id){swap(pos[i],id);swap(v[i],x);}x^=v[i];}} } struct query{int l,r,id;bool operator < (const query o){return r<o.r;} }q[N]; int ans[N],a[N]; inline int calc(int l){int res(0);for(int i=20;i>=0;i--){//printf("i=%d v=%d pos=%d\n",i,v[i],pos[i]);if((res&(1<<i))==0&&v[i]&&pos[i]>=l) res^=v[i];}return res; } int main(){ #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifn=read();for(int i=1;i<=n;i++) a[i]=read();m=read();for(int i=1;i<=m;i++){q[i].l=read();q[i].r=read();q[i].id=i;}sort(q+1,q+1+m);int pl(0);for(int i=1;i<=m;i++){while(pl<q[i].r){pl++;upd(a[pl],pl);}ans[q[i].id]=calc(q[i].l);//printf("(%d %d) id=%d\n",q[i].l,q[i].r,q[i].id);}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0; } /* 10 36 32 32 70 101 8 60 25 101 88 1 2 9 */

總結

以上是生活随笔為你收集整理的CF1100F Ivan and Burgers（线性基）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。