シンプルな問題設定ながら割と手間取った。
https://www.hackerrank.com/contests/kcpc-omedetooo/challenges/max-times-min
問題
N要素の整数列Aが与えられる。
この数列の全部分列において、最大値×最小値の総和を求めよ。
解法
分割統治法で解く。
以後、対象の部分列をA[L...R]とし、その中心にある値A[M]を含む部分列における値の総和を求めよう。
左端をMからLに徐々に動かしつつ、右端をM~Rにしたときの値の総和を一気に求めることを考えよう。
今処理中の左端をxとする。M番目より右側の要素について、最大値が更新される位置とその値、および最小値が更新される位置と値をdequeで持つ頃にする。
また、区間加算・区間和を取れるBITまたはSegTreeを持つ。
このBITのy番目の値は、A[x...y]の最大値およびA[x...y]の最小値の累積を取れるようにしたものとする。
初期状態では左端がM、右端がM~Rまで動く場合の総和を求めてあるとし、左端xがMから左に動いていくとき、その総和がどうなるかを考えよう。
仮にA[x]が最大値の更新位置を管理するdequeの先頭の値より大きい場合、その位置までは最大値がA[x]に更新される。
その場合、前者のBITを一律(A[x]-旧最大値)だけ加算すればよい。
その時、総和は(A[x]-旧最大値)から最小値の累積和の分だけ加算される。
最小値が更新される場合も同様である。
int N; ll A[202020]; ll ret; template<class V, int ME> class BIT_r { public: V bit[2][1<<ME]; BIT_r(){clear();}; void clear() {ZERO(bit);}; void update(int entry, V val0, V val1) { entry++; while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry; } void clear(int entry) { entry++; while(entry <= 1<<ME) bit[0][entry-1]=bit[1][entry-1]=0, entry += entry & -entry; } V total(int entry) { if(entry<0) return 0; int e=entry++; V v0=0,v1=0; while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry; return e*v0+v1; } void add(int L, int R, V val) { // add val to L<=x<=R update(L,val,-val*(L-1)); update(R+1,-val,val*R); } }; BIT_r<ll,19> btx,bty; void dfs(int L,int R) { if(L==R) { return; } else if(L+1==R) { ret+=A[L]*A[L]; return; } else if(L+2==R) { ret+=A[L]*A[L]; ret+=A[L+1]*A[L+1]; ret+=A[L]*A[L+1]; return; } int M=(L+R)/2; dfs(L,M); dfs(M+1,R); deque<pair<int,int>> X,Y; int a=A[M],b=A[M],i; ll sum=0; X.push_back({A[M],M}); Y.push_back({A[M],M}); for(i=M;i<R;i++) { if(A[i]>X.back().first) X.push_back({A[i],i}); if(A[i]<Y.back().first) Y.push_back({A[i],i}); btx.add(i,i,X.back().first); bty.add(i,i,Y.back().first); sum+=X.back().first*Y.back().first; } X.push_back({10101,R}); Y.push_back({0,R}); for(i=M;i>=L;i--) { while(A[i]>X.front().first) { int cur=X.front().first; X.pop_front(); int nex=X.front().first; if(A[i]>=nex) { btx.add(M,X.front().second-1,nex-cur); sum+=(nex-cur)*bty.total(X.front().second-1); } else { btx.add(M,X.front().second-1,A[i]-cur); sum+=(A[i]-cur)*bty.total(X.front().second-1); X.push_front({A[i],M}); break; } } while(A[i]<Y.front().first) { int cur=Y.front().first; Y.pop_front(); int nex=Y.front().first; if(A[i]<=nex) { bty.add(M,Y.front().second-1,nex-cur); sum+=(nex-cur)*btx.total(Y.front().second-1); } else { bty.add(M,Y.front().second-1,A[i]-cur); sum+=(A[i]-cur)*btx.total(Y.front().second-1); Y.push_front({A[i],M}); break; } } ret+=sum; } for(i=M;i<=R;i++) btx.clear(i), bty.clear(i); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; dfs(0,N); cout<<ret<<endl; }
まとめ
Codeforcesに多そうな問題。
AtCoderだと900ptぐらいあってもよさそう?