만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

방형구 탐색 (Easy)

면접 대비

시간 제한1초메모리 제한1024 MB

요약
한 줄로 늘어선 꽃의 종류가 주어질 때, 구간 안의 특정 종류 꽃 개수를 세고 구간의 꽃을 제거하는 질의를 처리합니다.
난이도

쉬움10점 중 3점

유형
배열, 시뮬레이션
정답자
아직 제출이 없습니다

문제

이 문제는 “방형구 탐색 (Hard)” 문제와 NN, QQ의 제한을 제외하면 같은 문제다.

세종이는 수행평가로 방형구 탐색을 하고 있다. 방형구는 1×N1\times N 크기의 격자 모양이며, 각 칸에는 1번부터 NN번까지 순서대로 번호가 붙어 있다. 방형구의 각 칸에는 꽃이 한 송이씩 피어 있다. 세종이가 사는 세상에는 1010억 가지 종류의 꽃이 있으며, 꽃의 종류마다 1부터 10910^9까지의 번호를 붙여 구분한다. 세종이는 선생님이 정해준 구간 안에 핀 특정 꽃의 개수를 조사해야 한다. 그런데 선생님은 변덕이 심해서 조사할 범위를 자주 바꾼다. 화가 난 세종이는 꽃을 밟아 없애기로 했다.

세종이의 수행평가를 위해 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 l r k: 방형구의 ll번 칸부터 rr번 칸까지의 꽃 중 종류가 kk인 꽃의 개수를 출력한다.
  • 2 l r: 세종이가 방형구의 ll번 칸부터 rr번 칸까지의 꽃을 밟아 없앤다.

입력

첫째 줄에 방형구의 크기를 나타내는 양의 정수 NN이 주어진다. (1≤N≤1 0001 \leq N \leq 1\,000)

둘째 줄에 공백으로 구분된 양의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 주어진다. AiA_i는 ii번 칸에 핀 꽃의 종류를 의미한다. (1≤Ai≤1091 \leq A_i \leq 10^{9})

셋째 줄에 쿼리의 수를 나타내는 양의 정수 QQ가 주어진다. (1≤Q≤10 0001 \leq Q \leq 10\,000)

넷째 줄부터 QQ개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. (1≤l≤r≤N1 \leq l \leq r \leq N; 1≤k≤1091 \leq k \leq 10^{9})

1번 쿼리는 하나 이상 주어진다.

출력

각 1번 쿼리마다 정답을 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    10
1 5 5 5 3 2 1 1 10 2
6
1 1 10 3
1 2 7 5
2 3 5
1 1 3 5
2 4 7
1 1 10 1
    예상 출력
    1
3
1
2