Codeforces #823 : Div2 E. Maximums and Minimums

ラスト2問が割と難しかった回。
https://codeforces.com/contest/1730/problem/E

問題

整数列Aが与えられる。
以下を満たす連続部分列は何通りか。

• 部分列中の最小値は最大値を割り切る

解法

各要素A[i]に対し、その要素が区間中最大値かつ最大値の中で初出となるような、左端と右端の範囲を求めておこう。
A[i]の約数を大きい順に総当たりし、その値が最小値となるような左端と右端の範囲を求めて行けばよい。

int T,N;
int LG[505050],RG[505050];
int LL[505050],RL[505050];
vector<int> di[1010101];
vector<int> D[1010101];
int pre[1010101];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-(1<<30);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){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]=comp(val[entry],v); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> stma,stmi;
int A[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=1000000;i++) {
		for(j=2*i;j<=1000000;j+=i) di[j].push_back(i);
	}
	
	cin>>T;
	while(T--) {
		
		FOR(i,1000100) D[i].clear(), pre[i]=-10000;
		
		cin>>N;
		FORR(v,stma.val) v=0;
		FORR(v,stmi.val) v=-(N+1);
		FOR(i,N) {
			cin>>A[i+1];
			D[A[i+1]].push_back(i+1);
			LG[i+1]=stma.getval(A[i+1],1<<20);
			LL[i+1]=stma.getval(0,A[i+1]);
			stma.update(A[i+1],i+1);
		}
		for(i=N;i>=1;i--) {
			RG[i]=-stmi.getval(A[i]+1,1<<20);
			RL[i]=-stmi.getval(0,A[i]);
			stmi.update(A[i],-i);
		}
		for(i=1;i<=1000000;i++) reverse(ALL(D[i]));
		
		ll ret=0;
		for(i=1;i<=N;i++) {
			int TL=LG[i],TR=RG[i];
			
			int AL=max(TL,LL[i]);
			int AR=min(TR,RL[i]);
			ret+=1LL*(i-AL)*(AR-i);
			
			FORR(d,di[A[i]]) {
				while(D[d].size()&&D[d].back()<i) {
					pre[d]=D[d].back();
					D[d].pop_back();
				}
				
				int SL=TL,SR=TR;
				if(pre[d]>TL&&RL[pre[d]]>i) SL=pre[d];
				if(D[d].size()&&LL[D[d].back()]<i) SR=D[d].back();
				
				//cout<<"#"<<d<<" "<<SL<<" "<<SR<<" "<<ret<<endl;
				if(SL>TL&&SR<TR) {
					int CL=max(TL,LL[SL]);
					int CR=min(TR,RL[SR]);
					ret+=1LL*(SL-CL)*(SR-i);
					ret+=1LL*(i-SL)*(CR-SR);
					ret+=1LL*(SL-CL)*(CR-SR);
				}
				else if(SL>TL) {
					int CL=max(TL,LL[SL]);
					int CR=min(TR,RL[SL]);
					ret+=1LL*(SL-CL)*(CR-i);
				}
				else if(SR<TR) {
					int CL=max(TL,LL[SR]);
					int CR=min(TR,RL[SR]);
					ret+=1LL*(i-CL)*(CR-SR);
				}
			}
			//cout<<i<<" "<<A[i]<<" "<<LG[i]<<" "<<LL[i]<<" "<<RG[i]<<" "<<RL[i]<<" "<<ret<<endl;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

解答を見てしまえばすんなりだけど、本番さっと出ないんだよね。