Codeforces ECR #152 : E. Max to the Right of Min

5問目から割と難しめ？
https://codeforces.com/contest/1849/problem/E

問題

1～NのPermutation Pが与えられる。
Pの連続部分列のうち、最大値が最小値の手前に現れるものは何通りか。

解法

右端をどんどん右にずらしていく際、左端を選ぶ場合に最大値または最小値が更新される位置の一覧を更新していこう。
最小値よりも最大値が先に現れるようなindexの個数の総和を取ればよい。

int N;
int P[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	set<pair<int,int>> S={{0,0}};
	ll ret=0;
	ll sum=0;
	vector<int> ma,mi;
	for(i=1;i<=N;i++) {
		cin>>P[i];
		while(ma.size()&&P[ma.back()]<P[i]) {
			auto it=S.lower_bound({ma.back(),0});
			if(next(it)->second==1) sum+=ma.back()-prev(it)->first;
			S.erase(it);
			ma.pop_back();
		}
		while(mi.size()&&P[mi.back()]>P[i]) {
			auto it=S.lower_bound({mi.back(),1});
			if(next(it)->second==0) sum-=mi.back()-prev(it)->first;
			S.erase(it);
			mi.pop_back();
		}
		ret+=sum;
		ma.push_back(i);
		mi.push_back(i);
		S.insert({i,0});
		S.insert({i,1});
	}
	cout<<ret<<endl;
	
}

まとめ

本番なんでこれ解けてないんだろ。