HDU 6579

tags:線性基,優化

題意

讓你在區間 \([l,r]\) 中選若干個數,使得異或和最大
支持末尾加入,區間查詢,強在

題解

可以暴力維護區間的線性基,但是會超時

考慮維護每個點的前綴線性基,線性基里將靠右的數字盡可能放高位,就是存一個額外存一個位置 p,表示這個位上的數的位置,從高位到低位掃,如果當前位置大于這個位上的位置那么交換,然后就得到了一個靠右的數字盡可能在高位的線性基

然后對于詢問 \([l,r]\) 在 \(r\) 的前綴線性基里找,只在位置大于等于 \(l\) 的位更新答案

#include<cstdio> #include<algorithm> #define int long long #define rep(i,a,b) for(int i=(a);i<=(b);++i) template<typename T>inline void rd(T&x){int fl=0,ch;while(ch=getchar(),ch<48||57<ch)fl^=!(ch^45);x=(ch&15);while(ch=getchar(),47<ch&&ch<58)x=x*10+(ch&15);if(fl)x=-x;} template<typename T>inline void pt(T x){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);} template<typename T>inline void pt(T x,int ch){pt(x),putchar(ch);} template<typename T>inline T max(const T&x,const T&y){return x<y?y:x;} template<typename T>inline T min(const T&x,const T&y){return x<y?x:y;} const int N=500005; int T,n,m,a[N],b[N][31],p[N][31]; void ins(int*b,int*p,int x,int pos){for(int i=30;~i;--i)if(x>>i&1){if(!b[i]){b[i]=x;p[i]=pos;break;}else{if(pos>p[i]){std::swap(b[i],x);std::swap(p[i],pos);}x^=b[i];}} } int qry(int*b,int*p,int pos){int res=0;for(int i=30;~i;--i)if(p[i]>=pos&&(res^b[i])>res)res^=b[i];return res; } signed main(){rd(T);while(T--){int n,m;rd(n),rd(m);rep(i,1,n){rd(a[i]);memcpy(b[i],b[i-1],sizeof(b[i]));memcpy(p[i],p[i-1],sizeof(p[i]));ins(b[i],p[i],a[i],i);}int lst=0;while(m--){int op;rd(op);if(op==0){int l,r;rd(l),rd(r);l=(l^lst)%n+1,r=(r^lst)%n+1;if(r<l)l^=r^=l^=r;pt(lst=qry(b[r],p[r],l),'\n');}else{rd(a[++n]);a[n]^=lst; memcpy(b[n],b[n-1],sizeof(b[n])); memcpy(p[n],p[n-1],sizeof(p[n]));ins(b[n],p[n],a[n],n);}}}return 0; }

轉載于:https://www.cnblogs.com/xay5421/p/HDU6579.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

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