방형구 탐색 (Hard)

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

요약
최대 200,000개 원소 배열에서 특정 꽃 종류의 구간 개수를 세는 질의와 구간 삭제 갱신을 처리한다.
난이도

어려움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개의 양의 정수 A_1,A_2,⋯ ,A_NA\_1,A\_2,\cdots ,A\_N이 공백으로 구분되어 주어진다. 이때 A_iA\_i는 ii번 칸에 핀 꽃의 종류를 의미한다. (1≤A_i≤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\leq l\leq r\leq N; 1≤k≤109)1\leq k\leq 10^{9})

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

출력

각 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