BOJ 13537 수열과 쿼리 1 (Persistent Segment Tree version)

 

문제 링크 : https://www.acmicpc.net/problem/13537

13537번: 수열과 쿼리 1

 

수열이 모두 입력되고 나서 쿼리가 따로 주어지므로 소위 off-line query로 해결하라는 거 같은데...

익숙해지면 persistent segment tree 가 구현하기 오히려 편하게 느껴진다.

 

persistent segment tree는 배열의 원소가 하나 추가될 때 마다 세그먼트 트리를 하나씩 만든다.

이 과정에서 메모리, 시간이 문제가 되니까, 갱신되는 경로 상의 node 는 새로 만들고 나머지는 이전 트리의 node를 가져다 쓴다.

 

#include<bits/stdc++.h>

using namespace std;

struct Node{
    int v;
    Node *nl, *nr;
    Node() : v{0}, nl{nullptr}, nr{nullptr} {}
    Node(int v, Node *l, Node *r) : v{v}, nl{l}, nr{r} {}
    
    Node* make(int il, int ir, int p){
        if(p<il || ir<p) return this;
        if(il==ir) return new Node(v+1, nullptr, nullptr);
        
        int mid=il+ir>>1;
        return new Node(v+1, nl->make(il,mid,p), nr->make(mid+1, ir, p));
    }
} *root[100001], *null;

int qry(int il, int ir, Node *S, Node *E, int p){
    if(p<il) return 0;
    if(ir<=p) return E->v - S->v;
    
    int mid=il+ir>>1;
    return qry(il,mid,S->nl, E->nl,p)+qry(mid+1, ir, S->nr, E->nr,p);
}

int arr[100001], cpy[100001];

int main(){
    int N; scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&arr[i]);
        cpy[i]=arr[i];
    }
    
    sort(cpy+1,cpy+N+1);
    int sz=unique(cpy+1, cpy+N+1)-cpy;
    
    null=new Node();
    null->nl=null->nr=null;
    
    for(int i=1;i<=N;i++){
        int p=lower_bound(cpy+1,cpy+sz,arr[i])-cpy;
        if(i==1) root[i]=null->make(0, sz, p);
        else root[i]=root[i-1]->make(0, sz, p);
    }
    
    int m; scanf("%d",&m);
        
    for(int i=0;i<m;i++){
        int a,b,k; scanf("%d%d%d",&a,&b,&k);
        int p=upper_bound(cpy+1, cpy+sz, k)-cpy;
        printf("%d\n", (b-a+1) - qry(0,sz, a==1?null:root[a-1], root[b], p-1));
    }
}

 

값의 크기에 따른 순서를 index를 이용해서 저장한다.

il, ir 은 index 의 좌우를 뜻한다.(index 범위를 나타낸다.)

sort, unique 로 소위 좌표 압축을 해서 크기 순서를 정한다.