傳送門

?題意

一個數組a有n個數 m個操作

操作① 詢問$[l,r]$區間的異或值

操作② 在數組末尾追加一個數x，數組長度變為$n+1$

其中$l,r$不直接給出，其中$l=l%n+1,r=r%n+1$

其中$x=x^lastans$($lastens$為上一次詢問的答案)

?思路

強制在線的線性基，

在線線性基就是在離線的基礎上多開一維

具體思路跟CF1100F的在線做法一樣,戳這里

記得處理一下$l,r,x$

?代碼

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=5e6+5; 4 int a[maxn]; 5 int p[maxn][40],base[maxn][40]; 6 int n,q; 7 int last; 8 9 void Insert(int k,int x,int pos) 10 { 11 for(int i=30;i>=0;i--) 12 { 13 if(x&(1<<i)) 14 { 15 if(!base[k][i]) 16 { 17 base[k][i]=x; 18 p[k][i]=pos; 19 return ; 20 } 21 else if(pos>p[k][i]) 22 { 23 swap(base[k][i],x); 24 swap(p[k][i],pos); 25 } 26 x^=base[k][i]; 27 } 28 } 29 } 30 31 int getMax(int l,int r) 32 { 33 int ans=0; 34 for(int i=30;i>=0;i--) 35 if(p[r][i]>=l) 36 ans=max(ans,ans^base[r][i]); 37 38 return ans; 39 } 40 41 void Solve() 42 { 43 for(int i=1;i<=n;i++) 44 { 45 memcpy(p[i],p[i-1],sizeof(p[i-1])); 46 memcpy(base[i],base[i-1],sizeof(base[i-1])); 47 48 Insert(i,a[i],i); 49 } 50 51 while(q--) 52 { 53 int op; 54 scanf("%d",&op); 55 if(op==0) 56 { 57 int l,r; 58 scanf("%d%d",&l,&r); 59 l=(l^last)%n+1,r=(r^last)%n+1; 60 if(l>r) 61 swap(l,r); 62 last=getMax(l,r); 63 printf("%d\n",last); 64 } 65 else 66 { 67 n++; 68 scanf("%d",&a[n]); 69 memcpy(p[n],p[n-1],sizeof(p[n-1])); 70 memcpy(base[n],base[n-1],sizeof(base[n-1])); 71 72 Insert(n,a[n]^last,n); 73 } 74 } 75 } 76 77 int main() 78 { 79 int t; 80 scanf("%d",&t); 81 while(t--) 82 { 83 last=0; 84 scanf("%d%d",&n,&q); 85 for(int i=1;i<=n;i++) 86 scanf("%d",a+i); 87 88 Solve(); 89 } 90 } View Code

?

轉載于:https://www.cnblogs.com/MMMinoz/p/11599704.html

總結

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

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