30515번 - 방형구 탐색 (Hard)

문제

이 문제는 ”방형구 탐색 (Easy)”문제와 $N,ドル $Q$의 제한을 제외하고 같은 문제다.

세종이는 수행평가로 방형구 탐색을 하고 있다. 방형구는 1ドル\times N$ 크기의 격자 모양이며, 각 칸에는 순서대로 1ドル$번부터 $N$번까지 번호가 붙어 있다. 방형구의 각 칸에는 꽃이 한 송이씩 피어 있다. 세종이가 사는 세상에는 10ドル$억 가지 종류의 꽃이 있으며, 꽃의 종류에 1ドル$부터 10ドル$억까지의 번호를 붙여 구분한다. 세종이는 선생님이 정해준 구간 안에 핀 특정 꽃의 개수를 조사해야 한다. 그러나 선생님은 변덕이 많기 때문에 조사해야 할 범위를 자주 바꾸었다. 이에 화가 난 세종이는 꽃을 밟아 없애기로 했다.

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

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

입력

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

둘째 줄에 $N$개의 양의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. 이때 $A_i$는 $i$번 칸에 핀 꽃의 종류를 의미한다. $(1\leq A_i\leq 10^{9})$

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

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

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

출력

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

제한

힌트