문제

문제 분석

Naive하게 풀면 어떨까?
가능한 [i, j]의 수열을 모두 조사하면 된다.
이중 루프로 구사할 수 있을 것이다.
시간 복잡도는 O(N^2)으로, 시간 내에 풀 수가 없다.

그러나 잘 생각해보면, i는 0~N-1 까지 한번씩 조사하는데, j는 매 i마다 다시 조사하여 중복이 발생한다.
이 부분을 해결하면 좋을 것 같다.

offline query의 원리를 생각할 수 있을 것 같다.
무작위의 range[i, j] 쿼리가 들어올 때, 이전 조사한 내용을 최대한 활용할 수 있는 순서로 쿼리를 처리하는 게 핵심이다.

i를 기준으로 j를 하나씩 올리며 가능한 범위를 찾고, 막히면 i를 증가시키고, 다시 재개할 수 있으면 j를 증가시키면 되겠다.
한마디로 two pointer algorithm을 사용하면 된다.

알고리즘

• two pointer

자료구조

결과

/*
two pointer 사용.
l, r 조절 연습!
*/
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> seq;
vector<bool> bAppear;

int main ( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N;

    seq.resize(N, 0);
    bAppear.resize(N+1, false );

    for ( int i = 0; i < N; i++ ){
        cin >> seq[i];
    }

    int64_t rst = 0;
    {
        int l = 0;
        int r = 0;
        while ( l < N ) {
            if ( r < N ){ // r <= N-1
                if ( bAppear[seq[r]] == true ){
                    rst += r - l;
                    bAppear[seq[l]] = false;
                    l++;
                }
                else {
                    bAppear[seq[r]] = true;
                    r++;
                }
            }
            else {
                rst += r - l;
                bAppear[seq[l]] = false;
                l++;
            }
        }
    }
    cout << rst;

    return 0;
}

Other