C++14(g++5.4) 解法, 执行用时: 237ms, 内存消耗: 29968K, 提交时间: 2020-01-29 20:54:57

#include <bits/stdc++.h>

using namespace std;

const int base = 1e6+10,maxn = 2e5+10;
int pre[base*4+100];
int st[maxn][25],a[maxn];

int solve(int l,int r)
{
	int k = log(r-l+1)/log(2);
	int ans = max(st[l][k],st[r-(1<<k)+1][k]);
	return ans;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d",&x);
		x += base;
		a[i] = max(a[i-1],pre[x]);
		st[i][0] = i - a[i];
		pre[x] = i;
	}
	
	for(int j = 1; (1<<j) <= n; j++)
	for(int i = 1; (i+(1<<j-1)) <= n; i++)
	st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
	
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		++l,++r;
		if(a[r] < l)
		{
			printf("%d\n",r-l+1);
			continue;
		}
		int p = lower_bound(a+1,a+1+n,l-1) - a;
		int ans = max(p-l,solve(p,r));
		printf("%d\n",ans);
	}
 } 

C++11(clang++ 3.9) 解法, 执行用时: 275ms, 内存消耗: 29664K, 提交时间: 2020-05-30 12:12:40

#include<bits/stdc++.h>
using namespace std;
const int base=1e6+10,maxn=2e5+10;
int pre[base*4+100];
int st[maxn][25],a[maxn];
int solve(int l,int r)
{
	int k=log(r-l+1)/log(2);
	int ans=max(st[l][k],st[r-(1<<k)+1][k]);
	return ans;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		x+=base;
		a[i]=max(a[i-1],pre[x]);
		st[i][0]=i-a[i];
		pre[x]=i; 
	}
	for(int j=1;(1<<j)<=n;j++)
	for(int i=1;(i+(1<<j-1))<=n;i++)
	st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		++l,++r;
		if(a[r]<l)
		{
			printf("%d\n",r-l+1);
			continue;
		}
		int p=lower_bound(a+1,a+1+n,l-1)-a;
		int ans=max(p-l,solve(p,r));
		printf("%d\n",ans);
	}
}