提出 #59632622

---

ソースコード 拡げる

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

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

template<class T>
struct merge_sort_tree{
    int n;
    vector<vector<T>> x;
    merge_sort_tree()=default;
    merge_sort_tree(const vector<T> &vec):n((int)vec.size()){
        x.resize(n*2);
        for(int i=0;i<n;i++)x[n+i]={vec[i]};
        for(int i=n-1;i;i--){
            merge(x[i*2].begin(),x[i*2].end(),x[i*2+1].begin(),x[i*2+1].end(),back_inserter(x[i]));
        }
    }
    
    int cntLess(int l,int r,T query)const{
        l+=n,r+=n;
        int ret=0;
        while(l<r){
            if(l&1){
                ret+=lower_bound(x[l].begin(),x[l].end(),query)-x[l].begin(),l++;
            }
            if(r&1){
                r--,ret+=lower_bound(x[r].begin(),x[r].end(),query)-x[r].begin();
            }
            l>>=1,r>>=1;
        }
        return ret;
    }
    
    int cntLesseq(int l,int r,T query)const{
        l+=n,r+=n;
        int ret=0;
        while(l<r){
            if(l&1){
                ret+=upper_bound(x[l].begin(),x[l].end(),query)-x[l].begin(),l++;
            }
            if(r&1){
                r--,ret+=upper_bound(x[r].begin(),x[r].end(),query)-x[r].begin();
            }
            l>>=1,r>>=1;
        }
        return ret;
    }

    int cntMore(int l,int r,T query)const{
        int tot=max<int>(0,min<int>(r,n)-max<int>(l,0));
        return tot-cntLesseq(l,r,query);
    }

    int cntMoreeq(int l,int r,T query)const{
        int tot=max<int>(0,min<int>(r,n)-max<int>(l,0));
        return tot-cntLess(l,r,query);
    }

    template<class OStream> friend OStream &operator<<(OStream &os,const merge_sort_tree &clt){
        os<<'[';
        for(int i=0;i<clt.n;i++)os<<clt.x[clt.n+i][0]<<',';
        return os<<']';
    }
};

int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int N,Q;cin>>N>>Q;
	vector<int> H(N);for(auto&&e:H)cin>>e;
	
	vector<pair<int,int>> v;
	vector<int> t(N,-1e9);
	for(int i=N-1;i>=0;i--){
		while(v.size()&&v.back().first<H[i]){
			t[v.back().second]=i-1;
			v.pop_back();
		}
		v.push_back({H[i],i});
	}

	merge_sort_tree<int> tr(t);

	while(Q--){
		int l,r;cin>>l>>r;
		l--;
		cout<<tr.cntLess(r,N,l)<<endl;
	}
}

提出情報

ジャッジ結果