백준 13544 수열과 쿼리 3

문제 URL : https://www.acmicpc.net/problem/13544

13544번: 수열과 쿼리 3

 

문제접근법 k보다 큰원소의 [i,j]라는 인덱스에서 k보다 큰 원소의 개수를 구하는문제입니다.

세그먼트트리를 이용할수있고 , 세그먼트트리를 만드는과정에서

분할된 노드들을 하나가 될때까지 만들어 그분할된 노드들을 다시 합쳐서 만드는 과정을

머지소트트리라고 하네요

 

처음에 풀었을때 정말 무식하게  init을 여러번 돌리면서 노드들을 추가한후

전부 sort를 돌렸는데 이게 과연 빠를꺼라 생각하지는 않았지만 예상보다는 조금 빠르게 나왔더군요

 

그러나, 이러한방법보다는 c++ merge라는 함수를 이용하는 방법을 알게됐는데

두 벡터 v1,v2가 있고 두벡터를 하나의 벡터로 합쳐 v3라는 벡터를 만들고싶을때 merge를 이용할수있습니다.

merge가 참으로 유용한게

v1,v2 벡터가 정렬이 되어있다면 합쳐진 v3도 정렬을 할수있습니다. 시간복잡도는 O(v1.size()+v2.size()) 만에 가능하기때문에 머지소트 트리를 만드는 과정에서 더빠르게 만들기위해선 merge를 사용하는것이 더효율적입니다.

 

머지소트 트리르 만들고나면 input조건대로 xor하면서 upper_bound를 이용해 해당 개수가 몇개인지를 쉽게 구할수있습니다.

 

소스코드 :

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

#define MAX 100000
vector<int> tree[MAX*4+1];
vector<int> v;
vector<tuple<int,int,int>> tv;
int n,m;
void init(int idx,int x,int s=1,int e=n,int node=1){
    if(!(s<=idx&&idx<=e))return;
    tree[node].push_back(x);
    if(s==e)return;
    int mid = (s+e)>>1;
    init(idx,x,s,mid,node*2);
    init(idx,x,mid+1,e,node*2+1);
}
int query(int l,int r,int k,int s=1,int e=n,int node=1){
    if(l>e||r<s)return 0;
    if(l<=s&&e<=r)return tree[node].end()-upper_bound(tree[node].begin(),tree[node].end(),k);
    int mid = (s+e)>>1;
    return query(l,r,k,s,mid,node*2)+query(l,r,k,mid+1,e,node*2+1);
}
void input(){
    cin>>n;
    v=vector<int>(n);
    for(int i=0;i<n;i++)cin>>v[i];
    int a,b,c;
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        tv.push_back({a,b,c});
    }
}
void solve(){
    for(int i=0;i<n;i++){
        init(i+1,v[i]);
    }
    for(int i=1;i<=MAX*4;i++)
        sort(tree[i].begin(),tree[i].end());
    int last_ans =0;
    for(auto[l,r,k]:tv){
        l^=last_ans;
        r^=last_ans;
        k^=last_ans;
        last_ans = query(l,r,k);
        cout<<last_ans<<"\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    input();
    solve();
}

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.