만드는 중입니다

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

방형구 탐색 (Hard)

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

요약
배열에서 구간의 값을 지우는 연산과 구간 안에서 특정 값의 개수를 세는 연산을 처리합니다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 해시맵, 이분 탐색, 배열
정답자
아직 제출이 없습니다

문제

이 문제는 "방형구 탐색 (Easy)" 문제와 NN, QQ의 제한을 제외하고 같다.

방형구는 1×N1\times N 크기의 격자 모양이다. 각 칸에는 11번부터 NN번까지 순서대로 번호가 붙어 있다. 각 칸에는 꽃이 한 송이씩 피어 있다. 세종이가 사는 세상에는 1010억 가지 종류의 꽃이 있으며, 꽃의 종류마다 11부터 1010억까지의 번호를 붙여 구분한다.

세종이는 선생님이 정해준 구간 안에 핀 특정 꽃의 개수를 조사해야 한다. 그런데 선생님이 조사 범위를 자주 바꾸었다. 이에 화가 난 세종이는 꽃을 밟아 없애기로 했다.

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

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

입력

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

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

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

넷째 줄부터 QQ개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. (1≤l≤r≤N; 1≤k≤109)(1 \leq l \leq r \leq N;\ 1 \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