yukicoder : No.1079 まお

なんでこんな問題設定なんだろ。MAOと関係ある？
https://yukicoder.me/problems/no/1079

問題

整数列Aと整数Xが与えられる。
以下を満たす部分列の総要素数を求めよ。

• 両端の和がXで、内部に最小値を1つだけ持つ。

解法

最小値の候補を小さい順に見ていく。
今見ている最小値をvとすると、vの位置でAを分割していこう。
例えば今A[i]=vとしたとき、R＞iかつA[R]≦A[i]である最小のRと、L＜iでかつA[L]≦A[i]である最大のRを考える。
これはsetを使えば容易に求められる。

L≦L'≦i≦R'≦Rとなる[L',R']を選ぶと、最小値が1つであるという条件は満たせる。
あとは両端の和がXという条件を考える。
区間内における、値に対応する要素の登場回数とその位置の和をmapで保持しよう。
A[i]を処理するとき、[L+1,R-1]に対するmapを、マージテクの要領で[L,i]と[i,R]に分割する。
また、小さい方の領域を走査して、和がXとなる要素とその数を数え上げよう。

int N,K;
int A[101010];

map<int,ll> C[101010],P[101010];
set<int> dead;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	A[0]=A[N+1]=1<<30;
	map<int,vector<int>> M;
	FOR(i,N) {
		cin>>A[i+1];
		M[A[i+1]].push_back(i+1);
		C[N+1][A[i+1]]++;
		P[N+1][A[i+1]]+=i+1;
	}
	
	dead.insert(0);
	dead.insert(N+1);
	
	ll ret=0;
	FORR(m,M) {
		reverse(ALL(m.second));
		FORR(v,m.second) {
			dead.insert(v);
			auto it=dead.find(v);
			int L=*prev(it);
			int R=*next(it);
			
			if(v-L>R-v) {
				swap(C[R],C[v]);
				swap(P[R],P[v]);
				for(i=v+1;i<R;i++) {
					C[v][A[i]]--;
					P[v][A[i]]-=i;
					C[R][A[i]]++;
					P[R][A[i]]+=i;
				}
				C[v][A[v]]--;
				P[v][A[v]]-=v;
			}
			else {
				for(i=L+1;i<v;i++) {
					C[R][A[i]]--;
					P[R][A[i]]-=i;
					C[v][A[i]]++;
					P[v][A[i]]+=i;
				}
				C[R][A[v]]--;
				P[R][A[v]]-=v;
			}
		}
		FORR(v,m.second) {
			auto it=dead.find(v);
			int L=*prev(it);
			int R=*next(it);
			
			if(v-L>R-v) {
				C[v][A[v]]++;
				P[v][A[v]]+=v;
				for(i=v;i<R;i++) ret+=(i+1)*C[v][K-A[i]]-P[v][K-A[i]];
				C[v][A[v]]--;
				P[v][A[v]]-=v;
			}
			else {
				C[R][A[v]]++;
				P[R][A[v]]+=v;
				for(i=L+1;i<=v;i++) ret+=P[R][K-A[i]]-(i-1)*C[R][K-A[i]];
				C[R][A[v]]--;
				P[R][A[v]]-=v;
			}
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

これ系CSAとCodeforcesに多い印象。