CPSCO2019 Session1 : H - Highest and Ends

言われてみればこれも典型か。
https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_h

問題

整数列Aが与えられる。
l≦m≦n、A[l]+A[m]+A[n]=XかつA[m]がA[l...l]中最大であるような(l,m,n)の組を求めよ。

解法

分割統治で解く。
今区間A[L..R]内のうち、M=(L+R)/2とし、l≦Mかつ(M+1)≦rであるような(l,m,r)を列挙しよう。
その後は、[L...M]と[(M+1)...R]を個別に細分化してみていけばよい。

MからLに向けlを小さくする方向に探索するのと、(M+1)からRに向けrを大きくする方向でともに探索し、左端ないし右端別にmax(A[l..M])やmax(A[(M+1)...r])を求め昇順に並べよう。

たとえば今右端rを探索し、A[(M+1)...r]の最大値がA[m]であったとする。
この場合、A[m]が最大となりかつA[r]が右端となるのは、A[l]=X-A[m]-A[r]のうち、A[l..M]中の最大値がA[m]以下であるものを列挙すればよい。
mが[l..M]の範囲にある場合も同様に求める。

int N,X;
int A[101010];

ll ret;


void dfs(int L,int R) {
	if(R<=L) return;
	if(L+1==R) {
		if(A[L]*3==X) ret++;
		return;
	}
	int M=(L+R)/2,i;
	dfs(L,M);
	dfs(M,R);
	
	
	map<int,vector<int>> lef,ri;
	int ma=0;
	for(i=M-1;i>=L;i--) {
		ma=max(ma,A[i]);
		lef[A[i]].push_back(ma);
	}
	
	FORR(m,lef) sort(ALL(m.second));
	ma=0;
	int nd=0;
	for(i=M;i<R;i++) {
		if(ma<A[i]) nd=0;
		ma=max(ma,A[i]);
		if(ma==A[i]) nd++;
		ri[A[i]].push_back(ma);
		int D=X-ma-A[i];
		if(lef.count(D)) ret+=1LL*nd*(lower_bound(ALL(lef[D]),ma+1)-lef[D].begin());
	}
	FORR(m,ri) sort(ALL(m.second));
	
	ma=nd=0;
	for(i=M-1;i>=L;i--) {
		if(ma<A[i]) nd=0;
		ma=max(ma,A[i]);
		if(ma==A[i]) nd++;
		int D=X-ma-A[i];
		if(ri.count(D)) ret+=1LL*nd*(lower_bound(ALL(ri[D]),ma+1)-ri[D].begin());
		
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>A[i];
	dfs(0,N);
	cout<<ret<<endl;
	
}

まとめ

l＜m＜nだったらもう少し楽なんだけどね。