HackerRank HourRank 25 : C. The Strange Function

面倒な解法に進んでしまい時間切れ。
https://www.hackerrank.com/contests/hourrank-25/challenges/the-strange-function

問題

整数列Aが与えられる。

とするとき、A(L,R)の最大値を求めよ。

解法

Rを徐々に増やしていきつつ、GCDの項と(sum-max)の項それぞれの候補を探索していこう。
Rを定めたとき、Lを小さくするほどgcd(A[L...R])は小さくなる。
なお、gcdの特性から、Lを変えても高々gcdの取りえる値はlog(A[R])通りである。
よって、GCDに関するSegmentTreeを構築し、gcd(A[L...R])が等しくなるLの範囲を二分探索で求めよう。
そしてgcd(A[L...R])が等しいLの範囲で(sum-max)の最大値を求めていく。

(sum-max)の部分だが、区間加算と区間最大値クエリが使えるSegTreeを使おう。
Rに対し、f(L) := (sum(A[L...R])-max(A[L...R]))を格納し、その区間最大値を求めるSegTreeを構築していこう。
Rをインクリメントすると、f(L)はいずれもA[R]だけ加算しなければならないので、f(0)～f(R-1)にA[R]を加算しよう。
一方、A[R]を右端とすることでmax(A[L...R])が変化する可能性があるが、これはスライド最小値の要領でスタックを用いて左端からの最大値の候補一覧を参照することで、max(A[L...R])の変化を追うことができる。
それに応じて、最大値が更新された区間に対しf(x)をその分減算していく。

int N;
int A[50505];
ll S[50505];

static ll const def=-1LL<<50;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=def;
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return __gcd(l,r);};
	
	SegTree_2(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_3<ll,1<<17>  stmax;
SegTree_2<int,1<<17> stgcd;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<ll,int>> S;
	S.push_back({1<<20,-1});
	
	ll ret=0;
	int L,R;
	FOR(R,N) {
		cin>>A[R];
		stmax.update(R,R+1,-def);
		stmax.update(0,R,A[R]);
		int prev=R;
		while(S.back().first<=A[R]) {
			x=S[S.size()-2].second+1;
			stmax.update(x,prev,S.back().first-A[R]);
			prev=x;
			S.pop_back();
		}
		S.push_back({A[R],R});
		stgcd.update(R,abs(A[R]));
		
		int now=abs(A[R]);
		prev=R;
		
		L=R;
		while(1) {
			for(i=17;i>=0;i--) {
				if(L-(1<<i)<0) continue;
				if(stgcd.getval(L-(1<<i),R+1)==now) L-=1<<i;
			}
			
			ret=max(ret,1LL*now*stmax.getval(L,prev+1));
			if(L==0 || now==0) break;
			L--;
			prev=L;
			now=stgcd.getval(L,R+1);
		}
		
	}
	
	cout<<ret<<endl;
}

まとめ

Stack解思いついたのになぁ。
面倒なSegTreeを作ろうとしたのが失敗だった。