Codeforces - 587e (linear basis + segment tree + difference)

The question ：n Number , Two kinds of operations , operation 1 Is interval XOR k, operation 2 Is to find the interval [l,r] Choose the number of different XORs and sums that any number can represent .

Ideas ： Operated by 2 It is not difficult to think of maintaining a linear basis on the line segment tree .
But because of the operation 1 It is interval modification , The merging of interval modified linear bases seems a little difficult ？
There is a very nb How to do it , XOR the array , In this way, operation 1 will be transformed into two single point modification operations . The linear basis of the difference array is equivalent to the original array .
The transformation method is as follows ：
Set the original array to a, The difference array is d, among d[i] = a[i]^a[i-1]
Suppose we're going to use d Array a[l…r] The linear base , Let's get a[l], Then add d[l+1], You can get a[l+1], And so on until you join d[r]. The obtained linear basis , Just like a[l…r] Is equivalent to ！（ Not in sequence ）. such , Maintain differential arrays , Then maintain the tree array a[i] Can quickly modify and maintain interval linear basis . Very awesome nature ！
On the combination of linear bases ： The most brainless realization is to add the elements in the linear basis of the left son and the right son to the linear basis of the father , Just... Anyway 30 The constant 233.
I didn't expect a difference during the game , This question is so awesome ！

#include<iostream>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define ldb long double
const int N = 2e5+5;
const int mx = 29;
int A[N],B[N];
int n;
struct TreeArray{
    
    int c[N],maxn;// It needs to be preset 
    int lowbit(int x){
    return x&(-x);}
    int sum(int i ){
    
        if( !i ) return 0;// need 0 Words , All of you +1
        int ans=0;
        while( i ){
    
            ans ^= c[i];
            i -= lowbit(i);
        }
        return ans;
    }
void add(int i ,int val){
    
        while( i<=maxn ){
    
            c[i] ^= val;
            i += lowbit(i);
        }
        return;
    } 
}ta;
struct LB{
    
    int a[30+1],temp[30+1];
    int siz=0;
    LB(){
    
        mst(a,0),mst(temp,0);
    }
    bool insert(int t){
    
        for(int i=mx ;i>=0; i--){
    
            if( !(t&(1<<i))) continue;
            if(!a[i]){
    
                a[i]=t;
                temp[++siz] = a[i];
                return true;
            }
            t ^= a[i];
        }
        return false;
    }
    void clear(){
    
        _for(i,0,mx){
    
           a[i]=0;
        }
        siz = 0;
    }
}L[N<<2];
void pu(int p){
    
    L[p].clear();
    _for(i,1,L[ls].siz) L[p].insert(L[ls].temp[i]);
    _for(i,1,L[rs].siz) L[p].insert(L[rs].temp[i]);
}
void build(int p,int l,int r){
    
    if( l==r ){
    
        L[p].insert(A[l]);
        return;
    }
    int mid = (l+r)>>1;
    build(lson),build(rson);
    pu(p);
}
void update(int p,int l,int r,int x,int wei){
    
    if( l==r ){
    
        A[l] ^= wei;
        L[p].clear();
        L[p].insert(A[l]);
        return;
    }
    int mid = (l+r)>>1;
    if( x<=mid ) update(lson,x,wei);
    else update(rson,x,wei);
    pu(p);
}
LB Q(int p,int l,int r,int x,int y){
    
    if( x<=l && r<=y ){
    
        return L[p];
    }
    int mid = (l+r)>>1;
    LB t1,t2,t3;
    if( x<=mid ) t1 = Q(lson,x,y);
    if( y>mid ) t2 = Q(rson,x,y);
    _for(i,1,t1.siz) t3.insert(t1.temp[i]);
    _for(i,1,t2.siz) t3.insert(t2.temp[i]);
    return t3;
}
signed main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    IOS;
    int q;
    cin>>n>>q;
    ta.maxn = n+2;
    _for(i,1,n) cin>>B[i];
    _for(i,1,n){
    
        A[i] = B[i]^B[i-1];
    }
    build(1,1,n);
    while( q-- ){
    
        int op;cin>>op;
        if( op==1 ){
    
            int l,r;cin>>l>>r;
            int x;cin>>x;
            ta.add(l,x);
            ta.add(r+1,x);
            update(1,1,n,l,x);
            if(r+1<=n) update(1,1,n,r+1,x);
        }
        else {
    
            int l,r;cin>>l>>r;
            int h = B[l]^ta.sum(l);
            if( l==r ){
    
                if( h ) h = 1;
                cout<<(1<<h)<<endl;
                continue;
            }
            auto ans = Q(1,1,n,l+1,r);
            int t = ans.siz;
            if( ans.insert(h) )t++;
            cout<<(1<<t)<<endl;
        }
    }
}