「bsoj1410」动态点数 - 二分+RMQ

题目大意

题目分析

我们首先二分一个长度，然后验证是否满足条件。
考虑$k$可能存在于区间什么位置，不难发现只可能是一个区间的最小值，因此我们得出思路一：二分长度，找出所有区间的最小值再扫描区间依次判断是否是其约数，时间复杂度$O(\frac{n^2}{4}\log n)$。

考虑一个区间若合法只可能是区间中存在它们的$gcd$，因此我们得出思路二：处理出区间$gcd$，二分长度后用数据结构判断是否存在该$gcd$，时间复杂度$O(n\log^2n)$。

考虑合并思路一与思路二，发现$k$只可能是区间最小值，也只可能是区间$gcd$，这是充要条件，因此我们可以用RMQ分别预处理出区间最小值与区间$gcd$，二分区间判断一下即可，时间复杂度$O(n\log n\log$常数$)$，这个常数是根据RP决定的，反正能过。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
int n,f1[500005][25],f2[500005][25],Ans[500005],ans=0;
int QueryMin(int Left,int Right) {
	int x=log2(Right-Left+1);
	return min(f1[Left][x],f1[Right-(1<<x)+1][x]);
}
int QueryGcd(int Left,int Right) {
	int x=log2(Right-Left+1);
	return __gcd(f2[Left][x],f2[Right-(1<<x)+1][x]);
}
void Sparse_Table() {
	for(int j=1; (1<<j)<=n; j++)
		for(int i=1; i+(1<<j)-1<=n; i++) {
			f1[i][j]=min(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
			f2[i][j]=__gcd(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
		}
}
bool Check(int len) {
	for(int i=1; i<=n-len+1; i++)
		if(QueryMin(i,i+len-1)==QueryGcd(i,i+len-1))return true;
	return false;
}
int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)f1[i][0]=f2[i][0]=Get_Int();
	Sparse_Table();
	int Left=1,Right=n;
	while(Left<=Right) {
		int mid=(Left+Right)>>1;
		if(Check(mid))Left=mid+1;
		else Right=mid-1;
	} 
	if(Right==1) {
		printf("%d 0\n",n);
		for(int i=1; i<=n; i++)printf("%d ",i);
		return 0;
	}
	for(int i=1; i<=n-Right+1; i++)
		if(QueryMin(i,i+Right-1)==QueryGcd(i,i+Right-1))Ans[++ans]=i;
	printf("%d %d\n",ans,Right-1);
	for(int i=1; i<=ans; i++)printf("%d ",Ans[i]);
	return 0;
}