[백준] 13537번 수열과 쿼리1

13537 수열과 쿼리1

문제

---

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

i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

입력

---

첫째 줄에 수열의 크기 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)

출력

---

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

---

풀이)

수열의 길이도 10만까지 되며, 쿼리의 수도 10만까지 주어질 수 있다.

-> for문으로 일일히 하기에는 시간 초과가 남

세그먼트 트리를 이용해 각 구간마다 수열의 구간 원소들을 미리 저장해야 한다.

수열의 길이가 10일때 각 구간?(index 1~10까지 존재할 때)

1~10

1~5,          6~10

1~3, 4~5    6~8, 9~10

... 이런식

참고 그림)

풀이 방법

1. 세그먼트 트리 노드에 각 구간에 해당하는 수열의 원소들을 저장한다.

2. 트리의 각 노드의 구간 원소들을 오름차순으로 정렬한다.

3. 쿼리를 입력받은 후, 세그먼트 트리를 이용해 k보다 큰 수들의 개수를 구한다.

 3.1 원하는 쿼리 구간과 현재 살펴보고 있는 구간이 중복되지 않으면 큰 수의 개수 0

 3.2 원하는 쿼리 구간과 현재 살펴보고 있는 구간이 완전히 겹쳐서 중복된다면 현재 구간에서 큰 수의 개수 구함

-> upper_bound()사용

 3.3 원하는 쿼리 구간과 현재 살펴보고 있는 구간이 일부만 겹친다면 원하는 쿼리 구간에 포함되지 않는 정보 제거 위해 재탐색

참고

세그먼트 트리 : https://comyoung.tistory.com/10

upper_bound(): https://comyoung.tistory.com/207

코드)

#include <stdio.h>
#include <algorithm>    
#include <vector>
using namespace std;
 
int N,M;
int i, j, k;
vector<int> tree[400001];
 
//tree에 데이터 삽입하는 함수
//삽입할 값 위치, 삽입 값, 시작노드번호, 현재구간[left,right]
void update(int pos, int val, int node, int left, int right) {
    if (pos <left || pos>right) return;
    tree[node].push_back(val);
    int mid = (left + right) / 2;
    if (left != right) {//리프노드가 아닐 경우, node 자식들로 들어감
        update(pos, val, node * 2, left, mid);
        update(pos, val, node * 2 + 1, mid + 1, right);
    }
}
 
//쿼리 구하는 함수
//찾는 구간[L,R], 시작노드번호, k ,현재노드구간[left,right]
int query(int L, int R, int node, int k, int left, int right) {
    //1. 현재구간이 찾고자 하는 구간과 전혀 겹치지 않을 때 -> k보다 큰 수 개수 0
    if (R < left || right < L) return 0;
    //2. 현재구간이 찾고자 하는 구간에 포함
    if (L <= left && right <= R) return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), k);
    //3. 현재구간이 찾고자 하는 구간에 일부 포함
    int mid = (left + right) / 2;
    return query(L, R, node * 2, k, left, mid) + query(L, R, node * 2 + 1, k, mid + 1, right);
}
 
int main()
{
    scanf("%d", &N);
    int temp = 0;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &temp);
        update(i, temp, 1, 1, N);//구간마다 값 삽입
    }
    for (int i = 0; i <= N * 4; i++)sort(tree[i].begin(), tree[i].end());//오름차순 정렬
    scanf("%d", &M);
    while (M--)
    {
        scanf("%d %d %d", &i, &j, &k);
        printf("%d\n", query(i, j, 1, k, 1, N));
    }
    return 0;
}