(13544) 수열과 쿼리 3

https://www.acmicpc.net/problem/13544

단계별로 풀어보기

52단계(세그먼트 트리 2) 9번째

 

 

 

머지 소트 트리를 구현하는 문제. 이 문제처럼 출력 쿼리가 어떤 값 이상, 이하 등을 요구하는 문제라면 머지 소트 트리가 정석일 가능성이 높다.

 

 

 

(정답 사진 업로드 깜빡함)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define ALL(v) (v).begin(), (v).end()

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, last= 0;
  
  cin >> n;
  
  vector<int> v(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  int treesize= (1<<(((int)ceil(log2(n+1)))+1));
  vector mstree(treesize, vector<int> ());
  
  auto init= [&](auto self, int s, int e, int node) -> void {
    if(s==e){
      mstree[node].push_back(v[s]);
    }else{
      self(self, s, s+(e-s)/2, node*2);
      self(self, s+(e-s)/2+1, e, node*2+1);
      
      mstree[node].resize(mstree[node*2].size()+mstree[node*2+1].size());
      merge(ALL(mstree[node*2]), ALL(mstree[node*2+1]), mstree[node].begin());
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r, int k) -> int {
    if(r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return  mstree[node].end()-upper_bound(ALL(mstree[node]), k);
    }else{
      long lsum= self(self, s, s+(e-s)/2, node*2, l, r, k);
      long rsum= self(self, s+(e-s)/2+1, e, node*2+1, l, r, k);
      return lsum+rsum;
    }
  };
  
  init(init, 1, n, 1);
  
  cin >> m;
  
  while(m--){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    a^= last;  b^= last;  c^= last;
    
    last= query(query, 1, n, 1, a, b, c);
    
    cout << last << "\n";
  }
  
  return 0;
}