description

analysis

这题出的失败在只卡正解不卡暴力
比较好想的方法是枚举约数，向两边二分，但是这个不满足二分性
首先用\(ST\)表维护区间的\(\gcd\)，不用线段树，这样查询就是\(O(\log_2(\max_{i=1}^{n} a_i))\)
然后照上面的方法做就行了，枚举约数，向左右二分，判断区间\(\gcd\)是否等于当前约数
时间复杂度\(O(n\log_2n)\)乘\(32\)的常数，注意卡常比如预处理出\(\log\)的值

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 500005

#define ll long long

#define reg register ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll f[MAXN][20],g[MAXN];

ll a[MAXN],ans[MAXN],LOG[MAXN];

ll n,mx,tot,cnt;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

inline ll query_gcd(ll l,ll r)

{

	ll k=LOG[r-l+1];

	return gcd(f[l][k],f[r+1-(1<<k)][k]);

}

int main()

{

	freopen("T2.in","r",stdin);

	//freopen("point.in","r",stdin);

	//freopen("point.out","w",stdout);

	n=read(),LOG[0]=-1;

	fo(i,1,n)a[i]=f[i][0]=read(),LOG[i]=LOG[i>>1]+1;

	fo(j,1,LOG[n])fo(i,1,n+1-(1<<j))

	f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);

	fo(i,1,n)

	{

		ll l=1,r=i,mid,tmp;

		while (l<=r)

		{

			mid=(l+r)>>1;

			query_gcd(mid,i)==a[i]?r=mid-1:l=mid+1;

		}

		tmp=l,l=i,r=n;

		while (l<=r)

		{

			mid=(l+r)>>1;

			query_gcd(i,mid)==a[i]?l=mid+1:r=mid-1;

		}

		if (r-tmp>mx){mx=r-tmp,ans[tot=1]=tmp;}

		else if (r-tmp==mx)ans[++tot]=tmp;

	}

	sort(ans+1,ans+tot+1);ll i=1;

	while (i<=tot)

	{

		g[++cnt]=ans[i];

		while (ans[i]==ans[i+1] && i<=n)++i;

		++i;

	}

	printf("%lld %lld\n",cnt,mx);

	fo(i,1,cnt)printf("%lld ",g[i]);

	return 0;

}

巴特西

【JZOJ6294】动态数点

description

analysis

code

最新文章

热门文章