AtCoder ABC #140 : E - Second Sum

ノーミスで行けて良かった。
https://atcoder.jp/contests/abc140/tasks/abc140_e

問題

整数列Aが与えられる。
長さ2以上の部分列の組み合わせに対し、2番目に大きな要素の総和を求めよ。

解法

数列の各値が、2番目に大きな要素としてカウントされるような部分列が何通りあるかを、要素の大きな順に見ていこう。
今A[x]を含む部分列において、A[x]が2番目となるのを数えよう。

この場合、A[x]の前か後ろに1個自身より大きな要素が含まれているような部分列を数え上げればいいことになる。
L1をA[L1]＞A[x]となるx未満の最大値とし、L2をA[L2]＞A[x]となるL1未満の最大値とする。
つまりL1,L2はA[x]の手前にある値がA[x]より大きな値を持つindexの最寄2つである。
同様に、R1をA[R1]＞A[x]となる(x+1)以上の最小値とし、R2をA[R2]＞A[x]となる(R1+1)以上の最小値とする。

区間[p,q]がA[x]を2番目とするのは、L1が含まれるL2＜p≦L1＜x≦q＜R1か、L1＜p≦x＜R1≦q＜R2となるケースである。
なのでA[x]**1を足していけばよい。

L1,L2,R1,R2の求め方だが、A[x]の大きい順に処理していき、処理済みのindexをmultisetに突っ込んでおくとlower_boundでどうにかなる。
番兵として0とN+1を2個ずつ入れておくと端の処理が楽になってなおよし。

int N;
multiset<int> S;
int P[101010];
vector<pair<int,int>> V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	S.insert(0);
	S.insert(0);
	S.insert(N+1);
	S.insert(N+1);
	
	FOR(i,N) {
		cin>>P[i+1];
		V.push_back({P[i+1],i+1});
	}
	sort(ALL(V));
	reverse(ALL(V));
	ll ret=0;
	FORR(v,V) {
		ll num=v.first;
		int id=v.second;
		auto it=S.lower_bound(id);
		int R1=*it++;
		int R2=*it--;
		it--;
		int L1=*it--;
		int L2=*it;
		ret+=num*(R2-R1)*(id-L1);
		ret+=num*(L1-L2)*(R1-id);
		S.insert(id);
	}
	cout<<ret<<endl;
}

まとめ

同じ要素が複数ないのはちょっと楽。
まぁあんまり難しくないけどね…。

*1:L2-L1)*(R1-x)+(R2-R1)*(x-L1