简单问题
  • 板块学术版
  • 楼主xqqQwQ_
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/7/1 18:23
  • 上次更新2023/10/27 22:08:51
查看原帖
简单问题
480934
xqqQwQ_楼主2022/7/1 18:23

不能在函数中开数组吗

还是说这个数组大小有限制?

#include<bits/stdc++.h>

#define MAXN 1000001

using namespace std;

int n,m,len;
int a[MAXN],num[MAXN],b[MAXN];
int st[MAXN],la[MAXN];
int ansn[MAXN],lis[MAXN];

struct que
{
	int l,r,ind;
}q[MAXN];

bool cmp(que a,que b)
{
	if((a.l-1)/len==(b.l-1)/len) return a.r<b.r;
	else return a.l<b.l;
}

int bl(int l,int r)
{
	int las[MAXN];
	for(int i=l;i<=r;i++) las[num[i]]=0;
	int ans=0;
	for(int i=l;i<=r;i++)
	{
		if(!st[num[i]]) las[num[i]]=i;
		ans=max(ans,i-las[num[i]]);
	}
	return ans;
}

int main()
{
	cin>>n;
	len=sqrt(n);
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		num[i]=a[i];
		b[i]=(i-1)/len+1;
	}
	cin>>m;
	for(int i=1;i<=m;i++) 
	{
		cin>>q[i].l>>q[i].r;
		q[i].ind=i;
	}
	sort(a+1,a+n+1);
	int k=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=n;i++) num[i]=lower_bound(a+1,a+k+1,num[i])-a;
	sort(q+1,q+m+1,cmp);
	for(int i=1,j=1;j<=b[n]&&i<=m;j++)
	{
		int nr=min(n,j*len);
		int l=nr;int r=nr+1;
		int cnt=0;
		int ans=0;
		for(;b[q[i].l]==j&&i<=m;i++)
		{
			if(b[q[i].r]==j)
			{
				ansn[q[i].ind]=bl(q[i].l,q[i].r);
				cout<<ansn[q[i].ind]<<endl;
				continue;
			}
			while(r<=q[i].r)
			{
				la[num[r]]=r;
				if(!st[num[r]]) 
				{
					st[num[r]]=r;
					lis[++cnt]=num[r];
				}				
				ans=max(ans,r-st[num[r]]);
				r++;
			}
			int tp=ans;
			while(l>=q[i].l)
			{
				if(!la[num[l]]) 
				{
					la[num[l]]=l;
					continue;
				}
				ans=max(ans,la[num[l]]-l);
				l--;
			}
			ansn[q[i].ind]=ans;
			while(l<nr)
			{
				if(la[l]==l) la[l]=0;
				l++;
			}
			ans=tp;
		}
		for(int i=1;i<cnt;i++) st[lis[i]]=la[lis[i]]=0;
	}
	for(int i=1;i<=m;i++) cout<<ansn[i]<<endl;
	return 0;
} 

bl函数中的第一条语句无法执行

但如果把MAXN改成100000又可以

为什么啊

2022/7/1 18:23
加载中...