「CF1237D」Balanced Playlist

转载大佬博客沉迷学习的LJY

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a[201010],ans[101010];
int maxx[201010][20],minn[201010][20];
int Maxx,Minn=2e9;
int ST_min(int l,int r)
{
	int len=r-l+1;
	int k=log2(len);
	if(a[minn[l][k]]<a[minn[r-(1<<k)+1][k]])
		return minn[l][k];
	return minn[r-(1<<k)+1][k];
}
int ST_max(int l,int r)
{
	int len=r-l+1;
	int k=log2(len);
	if(a[maxx[l][k]]>a[maxx[r-(1<<k)+1][k]])
		return maxx[l][k];
	return maxx[r-(1<<k)+1][k];
}
int get_min(int l,int r)
{
	int p=a[l-1];
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(2*a[ST_min(l,mid)]>=p)
			l=mid+1;
		else
			r=mid;
	}
	return l;
}
int get_max(int l,int r)
{
	int p=a[l-1];
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(a[ST_max(l,mid)]<p)
			l=mid+1;
		else
			r=mid;
	}
	return l;
}
int solve(int x)
{
	if(ans[x])
		return ans[x];
	int ans1=get_min(x+1,x+n);
	int ans2=get_max(x+1,x+n);
	if(ans1<ans2)
		return ans[x]=ans1-x;
	else
		return ans[x]=ans2-x+solve((ans2-1)%n+1);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i+n]=a[i];
		maxx[i][0]=minn[i][0]=i;
		maxx[i+n][0]=minn[i+n][0]=i+n;
		Maxx=max(Maxx,a[i]);
		Minn=min(Minn,a[i]);
	}
	if(Minn*2>=Maxx)
	{
		for(int i=1;i<=n;i++)
			printf("-1 ");
		return 0;
	}
	for(int k=1;k<=18;k++)
	{
		int len=1<<k;
		for(int i=1;i+len-1<=2*n;i++)
		{
			int j=i+len-1,m=j-(len>>1)+1;
			if(a[maxx[i][k-1]]>=a[maxx[m][k-1]])
				maxx[i][k]=maxx[i][k-1];
			else
				maxx[i][k]=maxx[m][k-1];
			if(a[minn[i][k-1]]<=a[minn[m][k-1]])
				minn[i][k]=minn[i][k-1];
			else
				minn[i][k]=minn[m][k-1];
		}
	}
	for(int i=1;i<=n;i++)
		ans[i]=solve(i);
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	return 0;
}