2019 다 대학 교육 대회 1-운영(구간 선형 기)

원제:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&cid=848
제목:
n 개의 수 를 제시 하 는 배열 은 두 가지 조작 이 있 습 니 다.

[l,r][l,r][l,r]에서 일부 수 를 선택 하여 차이 나 최대,출력 최대 치 를 선택 합 니 다

4.567917.배열 뒤에 하나의 숫자 를 넣는다
해석:
일부 수치 가 다 르 거나 가장 큰 것 을 선택 하면 선형 기 는 의심 할 여지 가 없다.선형 기 를 모 르 는 학생 은 나의 블 로 그 를 볼 수 있다.
우 리 는 모든 위치 가 왼쪽 에 있 는 31 개의 기본 위 치 를 유지 하 는 것 을 고려 합 니 다.만약 에 내 가 i-1 i-1 i-1 에서 왼쪽으로 31 개의 기본 위치 와 값 을 알 았 다 고 가정 하면그러면 i i 를 유지 할 때 높 은 곳 에서 낮은 곳 까지 31 개의 기 초 를 유지 합 니 다.
4.567917.만약 에 이 기반 이 이전에 나타 나 지 않 았 다 면 현재 수 를 이 자리 의 기반 으로 직접 선택 합 니 다
4.567917.나타 나 면 위 치 를 비교 합 니 다.우리 가 R R R 을 정 해 조회 할 때 기 초 는 오른쪽 에 있 을 수록 내 구간 에 떨 어 질 수 있 기 때문이다.그래서 오른쪽 을 기준 으로 왼쪽 의 값 을 다 르 게 하거나 나중에 아래로 업데이트 합 니 다
코드:

#include
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
const int maxn=1e6+5;
int ji[maxn][31];
int pos[maxn][31];

void deal(int n,int val){
    int nex=n;
    rep(i,0,30)ji[n][i]=ji[n-1][i],pos[n][i]=pos[n-1][i];
    rrep(i,30,0){
        if(val&(1<<i)){
            if(!ji[n][i]){
                ji[n][i]=val;pos[n][i]=nex;return;
            }
            if(pos[n][i]<nex){
                swap(val,ji[n][i]);
                swap(nex,pos[n][i]);
            }
            val^=ji[n][i];
        }
    }
}

int main(){
    int t;scanf("%d",&t);
    while(t--){
        int lst=0;
        int n,m;scanf("%d%d",&n,&m);
        rep(i,1,n){
            int val;scanf("%d",&val);
            deal(i,val);
        }
        while(m--){
            int f;scanf("%d",&f);
            if(f==1){
                int val;scanf("%d",&val);
                val^=lst;
                deal(++n,val);
            }
            else{
                int l,r;scanf("%d%d",&l,&r);
                l^=lst,r^=lst;
                l%=n,r%=n;
                l++,r++;
                if(l>r)swap(l,r);

                int ans=0;
                rrep(i,30,0){
                    if(pos[r][i]>=l){
                        if((ans^ji[r][i])>ans){
                            ans^=ji[r][i];
                        }
                    }
                }
                printf("%d
",ans);
                lst=ans;
            }
        }
    }
}