Codeforces 467(#267 Div2) E. Alex and Complicated Task

Codeforces データ構造 解をどれか一つ

問題

n項からなる数列a[i]が与えられる。a[i]の必ずしも連続しない部分列b[i]で、

  • 長さが4m
  • b[4k + 1] = b[4k + 3]
  • b[4k + 2] = b[4k + 4]

が成り立つもののうち、最長のものを一つ出力せよ。

制約条件

n≦5 * 10^5
-10^9≦a[i]≦10^9

方針

求める数列は、a b a b c d c d ...という形。
a[i] = xに対して、a[prev[i] ] = xなるprev[i]（同じ数の直前の出現）はすぐ求まる。
(prev[i], i)の範囲に出現するyであって、prev[i]以前の出現が最も右にあるもの（これをright[i]とする）がわかれば、
dp[i] = max{dp[j] | j＜right[i]} + 1という風にアップデートしながらDPできる。


このright[i]の効率のよい求め方がわからなかったので、
平方分割＋二分探索とかいう変なことをしたら無情にTLEした（悲しい）


単なるsegment treeのRMQを、更新順序を上手く工夫してやるだけでこのyはわかる。
RMQにiを小さい順にイテレートしながら、prev[i]を入れていくのであるが、
query(prev[i] + 1, i)を調べる前に、最後の出現がprev[i]より大きいyを入れないようにしてやればよい。


具体的には、ループがiまで来たときに初めてupdate(i, prev[i])をすればよい。
(i, next[i])に対するyの最右位置を求めるときは、query(i + 1, next[i])とすればよい。


経路復元が非常に面倒だけど頑張る。

ソースコード

int back[MX], dp[MX], right[MX];
inline void update(int x, int y){
	if(dp[x] >= dp[y] + 1) return;
	dp[x] = dp[y] + 1;
	back[x] = y;
}

int main(){
	
	scanf("%d", &n);
	rep(i, n) scanf("%d", a + i), v.pb(a[i]);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	rep(i, n) a[i] = lower_bound(all(v), a[i]) - v.begin();
	
	pos.resize(v.size());
	memset(back, -1, sizeof(back));
	memset(prev, -1, sizeof(prev));
	memset(right, -1, sizeof(right));
	
	
	SegTree<int> rmq(n);
	
	rep(i, n){
		if(pos[a[i]].size()) prev[i] = pos[a[i]].back();
		pos[a[i]].pb(i);
	}
	rep(i, n){
		const vi &v = pos[a[i]];
		int x = lower_bound(all(v), i) - v.begin();
		if(x + 1 < v.size()){
			right[v[x + 1]] = rmq.query(i + 1, v[x + 1], 0, 0, rmq.n);
			rmq.update(v[x + 1], i);
		}
	}
	
	rep(i, n){
		if(dp[i + 1] < dp[i]) dp[i + 1] = dp[i], back[i + 1] = -1;
		
		if(prev[i] >= 0 && prev[prev[i]] >= 0 && prev[prev[prev[i]]] >= 0)
			update(i + 1, prev[prev[prev[i]]]);
		
		if(right[i] >= 0) update(i + 1, right[i]);
	}
	
	vi ans;
	int mx = -1, mxi;
	rep(i, n + 1) if(back[i] >= 0 && mx < dp[i]) mx = dp[i], mxi = i;
	
	while(mx > 0){
		rep(i, 2) ans.pb(v[a[mxi - 1]]), ans.pb(v[a[back[mxi]]]);
		mx--; mxi = back[mxi];
		while(mxi >= 0 && (back[mxi] < 0 || dp[mxi] != mx)) mxi--;
	}
	reverse(all(ans));
	printf("%d\n", ans.size());
	rep(i, ans.size()) printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
	
	return 0;
}