src/segtree/merge_sort_tree.hpp

View this file on GitHub
Last update: 2025-12-30 15:03:15+09:00
Include: #include "src/segtree/merge_sort_tree.hpp"

Depends on

src/template.hpp

Verified with

src/test/aoj_2907.cpp

Code

#pragma once
#include "../template.hpp"

template<class S> struct merge_sort_tree {
    int n;
    vector<vector<S>> d;
    merge_sort_tree(vector<S>& a):n(__bit_ceil(si(a))),d(n*2){
        rep(i,si(a)) d[n+i]={a[i]};
        for(int i=n;--i;){
            merge(all(d[i*2]),all(d[i*2+1]),back_inserter(d[i]));
        }
    }
    int range_cnt(int l,int r,S& u){
        int ret=0;
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1) ret+=lower_bound(all(d[l]),u)-d[l].begin(),l++;
            if(r&1) --r,ret+=lower_bound(all(d[r]),u)-d[r].begin();
        }
        return ret;
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/segtree/merge_sort_tree.hpp"

template<class S> struct merge_sort_tree {
    int n;
    vector<vector<S>> d;
    merge_sort_tree(vector<S>& a):n(__bit_ceil(si(a))),d(n*2){
        rep(i,si(a)) d[n+i]={a[i]};
        for(int i=n;--i;){
            merge(all(d[i*2]),all(d[i*2+1]),back_inserter(d[i]));
        }
    }
    int range_cnt(int l,int r,S& u){
        int ret=0;
        for(l+=n,r+=n;l<r;l>>=1,r>>=1){
            if(l&1) ret+=lower_bound(all(d[l]),u)-d[l].begin(),l++;
            if(r&1) --r,ret+=lower_bound(all(d[r]),u)-d[r].begin();
        }
        return ret;
    }
};