[C++][백준 31563] 수열 회전과 쿼리

문제

접근 방법

특정 범위의 값은 누적 합으로 구하는 것이 효율적이다.
문제는 수열이 회전한다는 점이다.

기준점을 잡고 기준점만 옮기는 방식으로 회전을 대체할 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int N, Q, cmd, a, b, idx;
vector<ll> A;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> Q;

    A = vector<ll>(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        cin >> A[i];
        A[i] += A[i - 1];
    }

    while (Q--)
    {
        cin >> cmd >> a;
        if (cmd == 3)
        {
            cin >> b;

            a = (a - 1 + idx) % N;
            b = (b - 1 + idx) % N;

            if (a <= b) // 안쪽 범위
            {
                cout << A[b + 1] - A[a];
            }
            else // 바깥쪽 범위
            {
                cout << A[N] - A[0] - (A[a] - A[b + 1]);
            }
            cout << "\n";
        }
        else
        {
            idx += ((cmd == 1) ? -a : a);
            idx = (idx + N) % N;
        }
    }
    return 0;
}

풀이

맞은 사람은 적지만 그래도 순위권이니 기록했다.

누적 합을 구할 때 기준점을 옮기기 때문에 a가 b보다 클 경우도 생길 수 있다. 그럴 때는 전체 누적 합에서 포함되지 않는 부분을 빼주는 방식으로 해결해 주면 된다.