백준 13537 (C++) 수열과 쿼리 1

최초 업로드: 2025-09-06 13:00:01

최근 수정 시간: 2025-09-06 13:00:36

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] 수열과 쿼리 1

[문제 링크](https://www.acmicpc.net/problem/13537)

## 문제 설명

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

## 입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에는 쿼리 i, j, k가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ 109)

## 출력

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

## 풀이
머지 소트 트리를 사용하여 풀면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 400'001;

int _size=1;
vector<vector<int>> arr(MAX);

int getCnt(int L, int R, int val, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 if(R<nodeL || nodeR<L) return 0;
 if(L<=nodeL && nodeR<=R) return arr[nodeNum].end() - upper_bound(arr[nodeNum].begin(), arr[nodeNum].end(), val);
 int mid = (nodeL+nodeR)/2;
 return getCnt(L, R, val, nodeNum*2, nodeL, mid) + getCnt(L, R, val, nodeNum*2+1, mid+1, nodeR);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 while(_size<n) _size<<=1;
 _size<<=1;

for(int i=_size/2;i<_size/2+n;i++) {
 int a; cin >> a;
 arr[i].push_back(a);
 }
 for(int i=_size/2-1;i>0;i--) {
 int l=0, r=0;
 while(l<arr[i*2].size() || r<arr[i*2+1].size()) {
 if(r>=arr[i*2+1].size() || l<arr[i*2].size() && arr[i*2][l]<arr[i*2+1][r]) arr[i].push_back(arr[i*2][l++]);
 else arr[i].push_back(arr[i*2+1][r++]);
 }
 }

int m; cin >> m;
 while(m--) {
 int i, j, k; cin >> i >> j >> k;
 cout << getCnt(i-1, j-1, k) << '\n';
 }
}
```