BOJ 12844(XOR)풀이

solved.ac 난이도 :플래 3

www.acmicpc.net/problem/12844

12844번: XOR

 

이문제는 일반 세그 레이지에서 +를 XOR(^)로 바꿔주면 된다. 하지만 이렇게만 바꿨을 경우 틀리게 된다. tree[n]=lazytree[n]*(e-s+1); 이거를 

if((e-s+1)%2!=0){
	tree[n]^=lazytree[n];//*(e-s+1);
}

이렇게 바꿔주면 된다.

저렇게 바꿔 주는 이유는 어떤수를 a라고 했을 때 b로 xor을 짝수번 해주면 a가 나오기 때문이다.

그렇기 때문에 구간개수가짝수가 아닐 경우 xor을 해주는 것이다.

이제 바꾸고 난 뒤 제출해주면

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<long long>l(1000001);
ll a,tree_size;
ll seg(vector<ll>&tree,vector<ll>&lazytree,ll n,ll s,ll e){
    if(s==e){return tree[n]=l[s];}
    return tree[n]=seg(tree,lazytree,n*2,s,(s+e)/2)^seg(tree,lazytree,n*2+1,(s+e)/2+1,e);
}
void propagate(vector<ll>&tree,vector<ll>&lazytree,ll n,ll s,ll e){
    if(lazytree[n]!=0){
        if(s!=e){
            lazytree[n*2]^=lazytree[n];
            lazytree[n*2+1]^=lazytree[n];
        }
        if((e-s+1)%2!=0){
            tree[n]^=lazytree[n];//*(e-s+1);
        }
        lazytree[n]=0;
    }
}
ll max1(vector<ll>&tree,vector<ll>&lazytree,ll n,ll s,ll e,ll left,ll right){
    propagate(tree,lazytree,n,s,e);
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return tree[n];}
    return max1(tree,lazytree,n*2,s,(s+e)/2,left,right)^max1(tree,lazytree,n*2+1,(s+e)/2+1,e,left,right);
}
void change(vector<ll>&tree,vector<ll>&lazytree,ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(tree,lazytree,n,s,e);
    if(s1<=s&&e<=e1){lazytree[n]^=f;propagate(tree,lazytree,n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(tree,lazytree,n*2,s,(s+e)/2,s1,e1,f);
    change(tree,lazytree,n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=tree[n*2]^tree[n*2+1];
}
int main()
{
    ll b,c,d,q,k,gh,gk;
    scanf("%lld",&a);
    int h=(int)ceil(log2(a));
    tree_size=(1<<(h+1));
    int i;
    vector<ll>tree(tree_size);
    vector<ll>lazytree(tree_size);
    for(i=0;i<a;i++){scanf("%lld",&l[i]);}
    seg(tree,lazytree,1,0,a-1);
    scanf("%lld",&b);
    for(i=0;i<b;i++){
        scanf("%lld",&q);
        if(q==2){scanf("%lld %lld",&c,&d);printf("%lld\n",max1(tree,lazytree,1,0,a-1,c,d));}
        else{scanf("%lld %lld %lld",&c,&d,&gk);change(tree,lazytree,1,0,a-1,c,d,gk);}
    }
}