yukicoder : No.878 Range High-Element Query

ここまではすんなりでした。
https://yukicoder.me/problems/no/878

問題

数列においてある要素が高いとは、その手前にある値で自身より大きな値が無いものをいう。
ここで整数列Aが与えられる。

以下のクエリに答えよ。

• 区間[L...R]が与えられる。部分列A[L...R]において高い要素の数。

解法

まず、各要素について手前にある最寄より大きな値のindexを求めよう。
i番目の要素に対する前述の値をB[i]とする。
これは要素を大きい順にソートして、処理済みのindexのsetを使うと容易にできる。

区間A[L...R]において高い要素の数は、B[L...R]のうちL未満の物の数を数えればよいことになる。
このテクはこの前の問題でやったね。
yukicoder : No.877 Range ReLU Query - kmjp's blog

template<class V,int NV> class SegTree_1 {
public:
	vector<vector<V>> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val.resize(NV*2);};
	V getval(int x,int y,int v,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) {
			return lower_bound(ALL(val[k]),v+1)-val[k].begin();
		}
		return getval(x,y,v,l,(l+r)/2,k*2)+getval(x,y,v,(l+r)/2,r,k*2+1);
	}
	void set(int entry,V v) {
		val[entry+NV].clear();
		val[entry+NV].push_back(v);
	}
	void build() {
		for(int i=NV-1;i>=1;i--) {
			val[i].clear();
			int a=0,b=0;
			int x=i*2,y=i*2+1;
			while(a<val[x].size() || b<val[y].size()) {
				if(a==val[x].size()) {
					val[i].push_back(val[y][b++]);
				}
				else if(b==val[y].size()) {
					val[i].push_back(val[x][a++]);
				}
				else if(val[x][a]<val[y][b]) {
					val[i].push_back(val[x][a++]);
				}
				else {
					val[i].push_back(val[y][b++]);
				}
			}
		}
	}
};
SegTree_1<int,1<<18> st;

int N,Q;
int A[202020];
int lef[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	vector<pair<int,int>> V;
	FOR(i,N) {
		cin>>A[i+1];
		V.push_back({A[i+1],i+1});
	}
	set<int> did;
	sort(ALL(V));
	reverse(ALL(V));
	FORR(v,V) {
		auto it=did.lower_bound(v.second);
		if(it!=did.begin()) {
			it--;
			lef[v.second]=*it;
		}
		st.set(v.second,lef[v.second]);
		did.insert(v.second);
	}
	st.build();
	FOR(i,Q) {
		int T,L,R;
		cin>>T>>L>>R;
		cout<<st.getval(L,R+1,L-1)<<endl;
	}
	
}

まとめ

今回全体的に★低くない？と思ったらやっぱり上方修正されたね。