[Codeforces 1113C] Sasha and a Bit of Relax

[Codeforces 1113C] Sasha and a Bit of Relax

XOR 개념에 대한 기본적인 지식이 필요한 문제이다. 전체 n개의 수가 주어지고 길이가 짝수인 어느 구간을 설정할 때 그 구간의 처음~중간까지의 수를 모두 XOR한 값과 중간 이후~끝까지의 수를 모두 XOR한 값이 같은 구간이 총 몇 개 존재하는지 카운트하는 문제이다. 

이 문제를 풀기에 앞서 XOR이라는 연산의 특성에 대해서 생각해보자. XOR는 비트 차원의 연산으로 같은 자릿수의 비트 중에서 값이 다른 수가 단 하나라도 존재한다면 1이 되고, 모두 동일해야만 0이 되는 연산이다. 즉 a XOR b의 결과가 0이라면 a==b가 성립하고 이는 필요충분조건이다. 이를 확장해서 생각해보면 가 성립한다면 좌변과 우변의 값이 동일하다는 뜻이다. 좌변과 우변이 동일하다면 의 값도 0이된다. 

따라서 문제 상황을 바꿔보자면 어느 구간 [l,r]에 대해서 ==0인 구간이 총 몇 개인지 카운트 하면 되는 것이다.  이 계산 또한 배열의 첫 번째 원소부터 하나씩 값을 XOR 해나가면서 이전에 나온 적이 있었던 값이라면 XOR해서 0이 된다는 의미이므로 답에 더해주면 된다. 일종의 메모이제이션 기법인 셈이다.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 300009
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
 
 
int arr[SIZE];
int cnt[2][(1<<20)+10];
int main(){
    int n;    scanf("%d",&n);
 
    for(int i=1 ; i<=n ; i++)
        scanf("%d",&arr[i]);
 
    ll ans=0;
    int cur=0;
    cnt[0][0]=1;
    for(int i=1 ; i<=n ; i++){
        cur^=arr[i];
        ans+=cnt[i%2][cur];
        cnt[i%2][cur]++;
    }
 
    printf("%lld\n",ans);
 
    return 0;
}