[BOJ] 31563: 수열 회전과 쿼리 (C/C++)

문제 31563번: 수열 회전과 쿼리

길이가 $N$인 정수 수열 $[A_1,A_2,\dots,A_N]$이 주어진다. 이때 다음 쿼리를 수행하는 프로그램을 작성해보자.

• $1$ $k$: 수열을 오른쪽으로 $k$만큼 회전시킨다. 즉, $A_1$의 값은 $A_{N-k+1}$, $A_2$의 값은 $A_{N-k+2}$, $\dots$, $A_k$의 값은 $A_N$, $A_{k+1}$의 값은 $A_1$, $A_{k+2}$의 값은 $A_2$, $\dots$, $A_N$의 값은 $A_{N-k}$로 동시에 변한다.  
• $2$ $k$: 수열을 왼쪽으로 $k$만큼 회전시킨다. 즉, $A_1$의 값은 $A_{k+1}$, $A_2$의 값은 $A_{k+2}$, $\dots$, $A_{N-k}$의 값은 $A_N$, $A_{N-k+1}$의 값은 $A_1$, $A_{N-k+2}$의 값은 $A_2$, $\dots$, $A_N$의 값은 $A_k$로 동시에 변한다.  
• $3$ $a$ $b$: 수열의 $a$번째 수부터 $b$번째 수의 합을 출력한다. 즉, $\sum_{i=a}^b A_i$를 출력한다.

입력

첫 번째 줄에 수열의 길이 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $A_1,A_2,\dots,A_N$이 공백으로 구분되어 주어진다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

출력

$3$번 쿼리에 대한 결괏값을 한 줄에 하나씩 입력으로 주어진 순서대로 출력한다.

제한

• $2 \le N \le 200\,000$   
• $1 \le Q \le 200\,000$   
• $1 \le A_i \le 10^9$   
• $1 \le k \le N$   
• $1 \le a \le b \le N$  입력으로 주어지는 모든 수는 정수이다.  
• $3$번 쿼리는 한 번 이상 주어진다.

문제분석

문제 요구사항

• 임의의 연속된 구간 합을 구해야 함.
• 임의의 연속된 구간의 요소의 값이 변함.

따라서 변화하는 연속된 구간 합을 구하여야 함.

구현

쿼리 1,2 번에 따라 배열을 변화 시키지 않고 구간에 대응하기 위한 Bias(편향)값 추가
쿼리 3번 실행 시 범위에 Bias 추가하여 범위 지정 따라서 left>right인 case(경우) 처리 요구.
따라서 해당 방법 구현을 위하여 Segment Tree와 Prefix Sum 두 가지 방법 활용하여 구현.

증명

Case 01: Segment Tree

길이가 $n$인 수열의 Segment Tree의 Init 시간복잡도는 대략 $\boldsymbol{4n = O(n)}$
구간 합을 구하는 Query의 시간복잡도는 $\boldsymbol{O(log\ n)}$이 된다.
구간 합을 구하는 Query의 갯수를 $q$ 라고 한다면,
따라서 Segment Tree의 전체 시간 복잡도는 $\boldsymbol{O(n)+q*O(log\ n)}$이 된다.

Case 02: Prefix Sum

길이가 $n$인 수열의 Prefix Sum수열을 구하는 시간복잡도는 $\boldsymbol{n = O(n)}$의 시간 복잡도를 가진다.
구간 합을 구하는 연산의 시간복잡도는 $\boldsymbol{O(1)}$ 이 된다.
따라서 Prefix Sum의 전체 시간 복잡도는 $\boldsymbol{O(n)+O(1)}$이 된다.

코드

Segment Tree

#include <iostream>
#include <vector>
class SegTree {
  int nmax;
  std::vector<long long> tree;

 public:
  explicit SegTree(const std::vector<int>& v) {
    nmax = BitCeil(v.size());
    tree.assign(nmax << 1, 0);

    for (int i = 0; i < v.size(); ++i) {
      tree[i + nmax] = v[i];
    }
    for (int i = nmax - 1; i > 0; --i) {
      tree[i] = tree[i << 1] + tree[i << 1 | 1];
    }
  }

  const long long Query(int left, int right) {
    long long left_value = 0;
    long long right_value = 0;
    for (left += nmax, right += nmax + 1; left < right;
         left >>= 1, right >>= 1) {
      if (left & 1) {
        left_value += tree[left++];
      }
      if (right & 1) {
        right_value += tree[--right];
      }
    }
    return left_value + right_value;
  }

 private:
  const size_t BitCeil(size_t size) {
    size_t output_size = 1;
    while (size != 0) {
      output_size <<= 1;
      size >>= 1;
    }
    return output_size;
  }
};

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

  int N, Q;
  std::cin >> N >> Q;

  std::vector<int> v(N);
  for (auto& i : v) {
    std::cin >> i;
  }

  int bias = 0;
  SegTree seg_tree(v);

  for (int i = 0; i < Q; ++i) {
    int left, right;
    std::cin >> right >> left;
    if (right == 1) {
      bias -= left;
      bias %= N;
    } else if (right == 2) {
      bias += left;
      bias %= N;
    } else  // right ==3
    {
      left = (left + bias - 1) % N;
      left = left < 0 ? left + N : left;

      std::cin >> right;
      right = (right + bias - 1) % N;
      right = right < 0 ? right + N : right;

      if (left <= right) {
        std::cout << seg_tree.Query(left, right) << '\n';
      } else {
        std::cout << seg_tree.Query(left, N - 1) + seg_tree.Query(0, right)
                  << '\n';
      }
    }
  }

  return 0;
}

Prefix Sum

#include <iostream>
#include <vector>

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

  int N, Q;
  std::cin >> N >> Q;

  std::vector<int64_t> prefix_sum(N + 1);
  for (int i = 1; i < prefix_sum.size(); ++i) {
    int num;
    std::cin >> num;
    prefix_sum[i] = prefix_sum[i - 1] + num;
  }

  int bias = 0;
  for (int i = 0; i < Q; ++i) {
    int left, right;
    std::cin >> right >> left;
    if (right == 1) {
      bias -= left;
      bias %= N;
    } else if (right == 2) {
      bias += left;
      bias %= N;
    } else {
      left = (left + bias) % N;
      left = left <= 0 ? left + N : left;

      std::cin >> right;
      right = (right + bias) % N;
      right = right <= 0 ? right + N : right;

      if (left <= right) {
        std::cout << prefix_sum[right] - prefix_sum[left - 1] << "\n";
      } else {
        std::cout << prefix_sum.back() - prefix_sum[left - 1] +
                         prefix_sum[right]
                  << "\n";
      }
    }
  }
  return 0;
}