kmjp's blog

競技プログラミング参加記です

KCPCおめでとうコンテスト: G. Max times Min

シンプルな問題設定ながら割と手間取った。
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ぐらいあってもよさそう?