백준 12844 - XOR

https://www.acmicpc.net/problem/12844

 

힌트 1

세그먼트 트리의 lazy propagation을 이용하여 특정 구간에 대한 연산을 $O(logN)$ 시간 복잡도로 적용할 수 있다.

힌트2

xor의 연산 기호가 $\oplus$이고 임의의 원소 A에 대해

 

$A \oplus A = 0$

 

$A \oplus 0 = A$

 

이다. 이 성질을 lazy propagation에 적용할 수 있는가?

---

풀이

1번 쿼리를 보면 lazy propagation을 응용해야 하는 것을 알 수 있다.

 

xor 연산을 어떻게 적용할까? xor의 두 성질을 짚고 가자.

 

$A \oplus A = 0$

 

$A \oplus 0 = A$

 

이 성질을 통해 같은 수를 홀수 번 xor하면 A, 짝수 번 xor하면 0임을 알 수 있다.

 

즉, propagation 과정에서 xor할 구간의 길이가 홀수면 xor을 하고 짝수면 xor를 하지 않으면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
int ar[500001];

inline int mid(int s, int e) { return s + (e - s) / 2; }

template <typename T>
class lazy_segtree
{
private:
  vector<T> lazy, tree;
public:
  lazy_segtree(int n): lazy(n * 4), tree(n * 4) { init(1, 1, n); }

  T init(int node, int start, int end)
  {
    if (start == end) return tree[node] = ar[end];
    int m = mid(start, end);
    return tree[node] = init(node * 2, start, m) ^ init(node * 2 + 1, m + 1, end);
  }

  void propa(int node, int start, int end)
  {
    if (!lazy[node]) return;

    if ((end - start + 1) & 1)
      tree[node] ^= lazy[node];

    if (start != end)
      lazy[node * 2] ^= lazy[node], lazy[node * 2 + 1] ^= lazy[node];

    lazy[node] = 0;
  }

  void update(int node, int start, int end, int l, int r, T val)
  {
    propa(node, start, end);
  
    if (start > r || end < l) return;

    if (l <= start && end <= r)
    {
      lazy[node] ^= val;

      propa(node, start, end);

      if (start != end)
      {
        lazy[node * 2] ^= lazy[node];
        lazy[node * 2 + 1] ^= lazy[node];
      }

      return;
    }

    int m = mid(start, end);
    update(node * 2, start, m, l, r, val);
    update(node * 2 + 1, m + 1, end, l, r, val);
    tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
  }

  T query(int node, int start, int end, int l, int r)
  {
    propa(node, start, end);

    if (start > r || end < l) return 0;

    if (l <= start && end <= r) return tree[node];

    int m = mid(start, end);
    return query(node * 2, start, m, l, r) ^ query(node * 2 + 1, m + 1, end, l, r);
  }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; ++i)
      cin >> ar[i];
    
    lazy_segtree<int> segtree(n);
  
    cin >> m;

    for (int i = 0; i < m; ++i)
    {
      int order, a, b, c;
      cin >> order;

      if (order == 1)
      {
        cin >> a >> b >> c;

        ++a, ++b;
        segtree.update(1, 1, n, a, b, c);
      }
      else
      {
        cin >> a >> b;
        ++a, ++b;
        cout << segtree.query(1, 1, n, a, b) << '\n';
      }
    }
}

 

제출 기록