2019杭电多校第一场 HDU 6579

题意

给出一个初始序列，两种操作，一种是询问一个区间异或最大值，另一种是在序列末尾加一个数，强制在线。

题解

区间异或最大值要用线性基，考虑线段树套线性基

空间复杂度为 O ( n ⋅ l o g 2 n ) O(n\cdot log^2n) O(n⋅log2n)，又因为线性基合并为 O ( l o g 2 n ) O(log^2n) O(log2n)，所以时间复杂度为 O ( n ⋅ l o g 3 n ) O(n\cdot log^3n) O(n⋅log3n)

无法解决

考虑分块，256个数字为一个块，每个块建立一个线性基，并用 p r e [ i ] pre[i] pre[i]和 l a s [ i ] las[i] las[i]分别维护块内的前缀线性基和后缀线性基

用ST表维护一段区间的线性基

当询问 [ l , r ] [l,r] [l,r] 时，找到所属的块 [ b l , b r ] [bl,br] [bl,br]

如果 b l = b r bl=br bl=br，则在 [ l , r ] [l,r] [l,r] 暴力建立线性基

否则，ST表找到 [ b l + 1 , b r − 1 ] [bl+1,br-1] [bl+1,br−1]的线性基，再与 p r e [ r ] pre[r] pre[r]和 l a s [ l ] las[l] las[l]合并，就得到这段区间的线性基了

可以证明，空间和时间复杂度均为 O ( n ⋅ l o g 2 n ) O(n\cdot log^2n) O(n⋅log2n)，实际更小

代码

#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;

struct LB {
    int a[30];

    inline void clr() {
        memset(a, 0, sizeof a);
    }

    inline void ins(int x,int lim=29) {
        for (int i = lim; ~i; --i) {
            if (x >> i & 1) {
            if (!a[i]) { a[i] = x; return; }
            x ^= a[i];
            }
        }
    }

    inline int query() {
        int res = 0;
        for (int i = 29; ~i; --i) 
            if ((res ^ a[i]) > res) res ^= a[i];
        return res;
    }

    inline friend LB operator + (LB A,LB B) {
        for (int i = 29; ~i; --i) 
            if (B.a[i]) A.ins(B.a[i], i);
        return A;
    }
} f[3915][12],pre[N],las[N];

int a[N],lg[N];

LB query(int l,int r){
    if (l==r) return f[r][0];
    int t=lg[r-l];
    return f[r][t]+f[l+(1<<t)-1][t];
}
namespace IO{ 
    #define BUF_SIZE 100000 
    #define OUT_SIZE 100000 
    #define ll long long 
    bool IOerror=0; 
    inline char nc(){ 
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
        if (p1==pend){ 
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
            if (pend==p1){IOerror=1;return -1;} 
        } 
        return *p1++; 
    } 
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 
    inline void read(int &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
};
using namespace IO;
int main(){
    int T,n,m;
    read(T);
    for (int i=2;i<N;i<<=1) lg[i]=1; for(int i=1;i<N;i++) lg[i]+=lg[i-1];
    while(T--){
        read(n);read(m); int ans=0,cnt=0;
        for(int i=1;i<=n;i++) read(a[i]);
        for(int i=0;i+255<=n;i+=256){
            f[++cnt][0].clr(); LB x; x.clr();
            for (int j=0;j<256;j++) f[cnt][0].ins(a[i+j]),pre[i+j]=f[cnt][0];
            for (int j=255;~j;--j) x.ins(a[i+j]),las[i+j]=x;
        }
        if ((n&255)!=255){
            int t=n;
            while(t&255) t--; 
            pre[t].clr(); pre[t].ins(a[t]);
            for(int i=t+1;i<=n;i++)
                pre[i]=pre[i-1],pre[i].ins(a[i]);
        }
          
        for (int j=1;j<=lg[cnt];j++)
            for(int i=1;i<=cnt;i++) if (i-(1<<j)+1>0)
                f[i][j]=f[i][j-1]+f[i-(1<<j-1)][j-1];

        while(m--){
            int op,l,r;
            read(op);
            if (!op){
                read(l);read(r);
                l=(l^ans)%n+1;r=(r^ans)%n+1; if (l>r) swap(l,r);
                int bl=(l>>8)+1,br=(r>>8)+1; LB x; x.clr();
                if (bl==br){
                    for (int i=l;i<=r;i++) x.ins(a[i]);
                    ans=x.query();
                    printf("%d\n",ans);
                }else{
                    if (bl+1!=br) x=query(bl+1,br-1);
                    x=x+las[l]; x=x+pre[r];
                    ans=x.query();
                    printf("%d\n",ans);
                }
            } else {
                read(r); r=r^ans;
                a[++n]=r; 
                if ((n&255)==0) 
                    pre[n].clr();
                else 
                    pre[n]=pre[n-1];
                pre[n].ins(a[n]);
                
                if ((n&255)==255){
                    f[++cnt][0].clr();
                    for(int i=0;i<256;i++) f[cnt][0].ins(a[n-i]),las[n-i]=f[cnt][0];
                    for(int i=1;i<12;i++) if (cnt-(1<<i)+1>0)
                        f[cnt][i]=f[cnt][i-1]+f[cnt-(1<<i-1)][i-1];
                }
            }
        }
    }
    return 0;
}