[백준] Xor Sum

문제 : https://www.acmicpc.net/problem/13504

 

문제요약 : 각각의 테스트 케이스마다 수열의 연속된 부분 수열 중 XOR 합이 가장 큰 부분 수열의 XOR 합을 출력한다

 

조건 :

1. 테스트 케이스 수 1 ≤ T ≤ 10

2. 수열 크기 1 ≤ N ≤ 100,000

3. 수열의 각 숫자는 int 범위 안의 음이 아닌 정수 (=32비트 안의 음이 아닌 정수)

 

해설 :

풀다가 힘들어서 다른 블로그를 참조했다...

https://young02.tistory.com/62

XOR 합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    node *x, *y;
    node(node *a, node *b){x=a; y=b;}
};
node *root=new node(NULL, NULL);
void insert(node *w, ll bits, ll pos){
    if(pos==-1) return;
    if((1<<pos)&bits) {
        if(w->y==NULL) w->y=new node(NULL, NULL);
        insert(w->y, bits, pos-1);
    }
    else {
        if(w->x==NULL) w->x=new node(NULL, NULL);
        insert(w->x, bits, pos-1);
    }
}
ll query(node *t, ll a, ll pos, ll p){
    if(pos==-1) return p;
    if((1<<pos)&a){
        if(t->x==NULL) return query(t->y, a, pos-1, p);
        else return pow(2,pos)+query(t->x, a, pos-1, p);
    }
    else{
        if(t->y==NULL) query(t->x, a, pos-1, p);
        else return pow(2,pos)+query(t->y, a, pos-1, p);
    }
}
int main(){
    ll n, m, c;
    for(scanf("%lld",&n); n--;){
        ll cxor=0, pr=0;
        scanf("%lld",&m);
        vector<ll> t;
        for(ll i=0; i<m; i++){
            scanf("%lld", &c);
            cxor^=c;
            t.push_back(cxor);
            pr=max(pr,cxor);
        }
        for(ll i=0; i<t.size(); i++){
            insert(root, t[i], 31);
            pr=max(pr,query(root, t[i], 31, 0));
        }
        printf("%d\n",pr);
        root=new node(NULL, NULL);
    }
    return 0;
}