Codeforces #630 Div2 G. No Monotone Triples

Div2 onlyなのにGもあるのか。
http://codeforces.com/contest/1332/problem/G

問題

整数列Aが与えられる。
ある3つの整数の組(i,j,k)が単調であるとは、A[i]・A[j]・A[k]がこの順に単調増加か単調減少のいずれかであることを示す。

ここで以下のクエリに答えよ。
クエリでは区間[L,R]が与えられる。
A[L...R]の部分列のうち、単調な組を持たない最長のものを求めよ。

解法

長さ5以上の数列は必ず単調な組を持つ。
そこで、各要素を右端とする、長さ3または4の単調でない組を事前に列挙しておこう。

長さ3の組の列挙方法として、数列の中身を例えば小さい順に処理していこう。
今添え字Mを処理しており、左右に最寄りの自身より小さい要素がL,R番目にあるなら、[L,M,R]が単調でない組の候補になる。
同様に大きい順にも処理を行っておく。

長さ4の組は、真ん中の2要素が最大値と最小値となる。
そこで左端Lを総当たりし、Lの右側にあるLより大きな要素XのうちXが以降により小さい要素Zがあり、Lより小さなYのうちY以降により大きい要素があるようなX,Yを選ぼう。
X,Yの候補はスライド最小値/最大値の要領で管理していく。

int N,Q;
int A[202020];
vector<int> cand3[202020];
vector<int> cand4[202020];
vector<pair<int,int>> U,D;
set<int> US,DS;
set<int> S;
int mo[202020],le[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	
	vector<pair<int,int>> V;
	FOR(i,N) {
		scanf("%d",&A[i]);
		V.push_back({A[i],i});
	}
	
	sort(ALL(V));
	
	FOR(i,2) {
		set<int> S;
		S.insert(-1);
		S.insert(N);
		FOR(x,N) {
			for(y=x;y<N&&V[y].first==V[x].first;y++) {
				int t=V[y].second;
				int R=*S.lower_bound(t);
				int L=*prev(S.lower_bound(t));
				if(L>=0 && R<N && (cand3[R].empty()||cand3[R][0]<L)) cand3[R]={L,t,R};
			}
			for(y=x;y<N&&V[y].first==V[x].first;y++) {
				S.insert(V[y].second);
			}
			x=y-1;
		}
		reverse(ALL(V));
	}
	
	U.push_back({1<<30,N});
	D.push_back({-(1<<30),N});
	US.insert(N);
	DS.insert(N);
	S.insert(N);
	vector<int> W;
	for(i=N-1;i>=0;i--) {
		while(U.back().first<A[i]) {
			if(DS.count(U.back().second)==0) S.insert(U.back().second);
			US.erase(U.back().second);
			U.pop_back();
			
		}
		while(D.back().first>A[i]) {
			if(US.count(D.back().second)==0) S.insert(D.back().second);
			DS.erase(D.back().second);
			D.pop_back();
		}
		
		if(A[i]==U.back().first) mo[i]=mo[U.back().second];
		else mo[i]=U.back().second;
		if(A[i]==D.back().first) le[i]=le[D.back().second];
		else le[i]=D.back().second;
		
		
		y=*S.lower_bound(max(mo[i],le[i]));
		U.push_back({A[i],i});
		D.push_back({A[i],i});
		US.insert(i);
		DS.insert(i);
		if(A[i]==A[i+1]) continue;
		if(y<N && cand4[y].empty()) {
			x=*prev(US.lower_bound(y));
			j=*prev(DS.lower_bound(y));
			if(x>i && j>i && x<y && j<y) cand4[y]={i,min(x,j),max(x,j),y};
		}
	}
	
	
	vector<int> ok3={-1,-1,-1},ok4={-1,-1,-1,-1};
	FOR(i,N) {
		if(cand3[i].size()) ok3=max(ok3,cand3[i]);
		cand3[i]=ok3;
		if(cand4[i].size()) ok4=max(ok4,cand4[i]);
		cand4[i]=ok4;
	}
	
	FOR(i,Q) {
		int L,R;
		scanf("%d%d",&L,&R);
		L--;
		R--;
		if(cand4[R][0]>=L) {
			cout<<4<<endl;
			cout<<cand4[R][0]+1<<" "<<cand4[R][1]+1<<" "<<cand4[R][2]+1<<" "<<cand4[R][3]+1<<endl;
		}
		else if(cand3[R][0]>=L) {
			cout<<3<<endl;
			cout<<cand3[R][0]+1<<" "<<cand3[R][1]+1<<" "<<cand3[R][2]+1<<endl;
		}
		else {
			cout<<0<<endl;
			cout<<endl;
		}
	}
}

まとめ

考え方はともかく、実装は割と面倒。