Codeforces 359D - Pair of Numbers

問題文

Pair of Numbers

概要

長さ$n$ の列が与えられる. 次の性質を満たす最長の部分列をすべて求めよ.

• $a_l,\ a_{l+1},\ \cdots,\ a_r$ を全て割り切る$a_j\ (l \leqq j \leqq r)$ が存在する.

$1 \leqq n \leqq 3 \times 10^5,\ 1 \leqq a_i \leqq 10^6$

解法

まず, 問題の性質を満たすような$a_j$ は部分列中の最小値であり, その部分列のgcd の値になっていないと行けない.
また, 長さ$x$ の列が実現できれば明らかに長さ$x - 1$ の列が実現できるので二分探索が可能である.
区間のgcd と最小値はSpare tree を使うことでそれぞれ$o(\log n), O(\log n)$ 時間で求まるから, $O(n \log ^2 n)$ 時間で問題を解くことが出来る.

コード

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int segA[300000][19], segB[300000][19];

void init()
{
	for (int i = 1; (1 << i) <= n; i++){
		for (int j = 0; j + (1 << (i - 1)) < n; j++){
			segA[j][i] = min(segA[j][i - 1], segA[j + (1 << (i - 1))][i - 1]);
			segB[j][i] = __gcd(segB[j][i - 1], segB[j + (1 << (i - 1))][i - 1]);
		}
	}
}

int gcds(int a, int b, int x)
{
	return (__gcd(segB[a][x], segB[b - (1 << x) + 1][x]));
}

int mins(int a, int b, int x)
{
	return (min(segA[a][x], segA[b - (1 << x) + 1][x]));
}

vector<int> check(int d)
{
	vector<int> ret;
	int x = 31 - __builtin_clz(d);
	if (d == 0) x = 0;
	for (int i = 0; i + d < n; i++){
		if (gcds(i, i + d, x) == mins(i, i + d, x)) ret.push_back(i + 1);
	}
	return (ret);
}

int main()
{
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		int x;
		scanf("%d", &x);
		segA[i][0] = segB[i][0] = x;
	}
	
	init();
	
	int lo = 0, hi = n - 1;
	
	while (lo != hi){
		int mid = (lo + hi + 1) >> 1;
		if (check(mid).size()) lo = mid;
		else hi = mid - 1;
	}
	
	vector<int> ans = check(lo);
	printf("%d %d\n", ans.size(), lo);
	for (int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], " \n"[i + 1 == ans.size()]);
	
	return (0);
}