なんでこんな問題設定なんだろ。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に多い印象。