Codeforces #1102 : Div2. F. Vessels, Heights and Two Versions (Hard Version)

本番はEasyを飛ばして最初からHardに行ってました。
https://codeforces.com/contest/2234/problem/F

問題

N要素の整数列Hが与えられる。
ここで、整数列Wを定めることを考える。
Wは以下の条件を満たさなければならない。

• max(W[i],W[(i+1)%N])＞H[i]の場合、W[i]=W[(i+1)%N]でなければならない。

W[i]=0としたとき、取りうるWの総和の最大値を各iごとに求めよ。

解法

H,Wをrotateして、W[0]=0のケースを考える。
実験すると、以下のことがわかる。

• Hの最大値のうち、indexが最小のものをH[p]とする。
• 解は、H[0]...H[p-1]のprefix maximumの総和と、reverse(H[p+1]....H[N-1])のprefix maximumの総和の合計

そこで、Hの各値に対し、その点をはじめとして左右両方向に、prefix maximumがH[p]に到達するまでの要素数のその総和をあらかじめ計算しておこう。
そうすればW[i]=0としたときの値はO(1)で求められる。

int T,N,H[203030];

int nex[202020];
int nex2[202020];
ll sum[202020];
int nexR[202020],nexR2[202020];
ll sumR[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int ma=0;
		FOR(i,N) {
			cin>>H[i];
			if(H[i]>H[ma]) ma=i;
		}
		vector<int> V;
		FOR(j,N) {
			x=ma-j;
			if(x<0) x+=N;
			while(V.size()&&H[V.back()]<=H[x]) V.pop_back();
			if(V.empty()) {
				nex[x]=nex2[x]=x;
				sum[x]=0;
			}
			else {
				nex[x]=V.back();
				nex2[x]=nex2[nex[x]];
				sum[x]=sum[nex[x]];
				int dif=V.back()-x;
				if(dif<0) dif+=N;
				sum[x]+=1LL*H[x]*dif;
			}
			V.push_back(x);
		}
		V.clear();
		FOR(j,N) {
			x=ma+j;
			if(x>=N) x-=N;
			while(V.size()&&H[V.back()]<=H[x]) V.pop_back();
			if(V.empty()) {
				nexR[x]=nexR2[x]=x;
				sumR[x]=0;
			}
			else {
				nexR[x]=V.back();
				nexR2[x]=nexR2[nexR[x]];
				sumR[x]=sumR[nexR[x]];
				int dif=x-V.back();
				if(dif<0) dif+=N;
				sumR[x]+=1LL*H[x]*dif;
			}
			V.push_back(x);
		}
		
		
		FOR(i,N) {
			ll ret=0;
			if(H[i]==H[ma]) {
				j=(i+N-1)%N;
				ret+=sumR[j];
				x=nexR2[j];
				int tar=i;
				int dif=x-tar;
				if(dif) {
					if(dif<0) dif+=N;
					ret+=1LL*(dif)*H[ma];
				}
			}
			else {
				ret+=sum[i];
				int tar=nex2[i];
				j=(i+N-1)%N;
				ret+=sumR[j];
				x=nexR2[j];
				int dif=x-tar;
				if(dif) {
					if(dif<0) dif+=N;
					ret+=1LL*(dif)*H[ma];
				}
				
			}
			cout<<ret<<" ";
		}
		
		cout<<endl;
		
	}
}

まとめ

特徴をつかむまでにだいぶ手間取った。