7088

static int N, Q, L, R;
static int cowlist[3 + 1][100000 + 1];
 
static void solution(void)
{
    int tmp;
 
    scanf("%d %d", &N, &Q);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &tmp);
        for (int j = 1; j <= 3; j++)
        {
            if (j == tmp)
                cowlist[j][i] = cowlist[j][i - 1] + 1;
            else
                cowlist[j][i] = cowlist[j][i - 1];
        }
    }
    for (int i = 1; i <= Q; i++)
    {
        scanf("%d %d", &L, &R);
        for (int j = 1; j <= 3; j++)
        {
            if (L == 1)
                printf("%d ", cowlist[j][R]);
            else if (cowlist[j][L] > cowlist[j][L - 1])
                printf("%d ", cowlist[j][R] - cowlist[j][L] + 1);
            else
                printf("%d ", cowlist[j][R] - cowlist[j][L]);
        }
        puts("");
    }
}

8191번 문제를 풀면서 사용한 방법을 약간 변형해서 적용 하였다.

입력으로 받은 L 에서 R을 반복문에 넣어서 답을 구하면 샘플 테스트케이스에서는 원하는 답을 구할 수 있었지만, 실제 테스트에서는 제한시간 초과가 발생하였다.

 

그래서 최대한 저 L ~ R의 순환하는 반복을 사용하지 않고 문제를 풀 수 있는 방법을 고안한 것이다.

 

L == 1 이면 별로 고민 할 게 없다.

 

[L - 1] < [L] 이면 L번째 송아지는 해당 그룹에 존재하는 것이기 때문에 +1을 해주어야 하고

그렇지 않다면 해당 송아지는 해당 그룹에 존재하지 않기 때문에 제외 해주는 것이 맞는 것이다.