BOJ 31563 : 수열 회전과 쿼리

• 문제 링크 : http://boj.kr/31563
• 난이도 : S2
• 태그 : 누적합

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<ll> arr(2*n+1);
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        arr[i+n] = arr[i];
    }
    for(int i = 1; i < arr.size(); i++) {
        arr[i] += arr[i-1];
    }
    int p = 0;
    for(int i = 0; i < q; i++) {
        int qa, a, b;
        cin >> qa;
        if(qa == 1) {
            cin >> a;
            p = (p-a+n)%n;
        }
        if(qa == 2) {
            cin >> a;
            p = (p+a)%n;
        }
        if(qa == 3) {
            cin >> a >> b;
            a = (a+p-1) % n + 1;
            b = (b+p-1) % n + 1;
            if(b < a) b += n;
            cout << arr[b] - arr[a-1] << "\n";
        }
    }

    return 0;
}

---

풀이

회전 쿼리를 받으면 배열을 실제로 회전시키지 않고 배열의 기준점을 바꿔준다.

탐색 쿼리를 받으면 바뀐 기준점을 통해 실제 위치를 구해주고, 누적합을 이용해 합을 구해준다.

원순열의 개념과 유사하므로 배열을 두배로 복사하여 구현하면 쉽게 구현할 수 있다.