http://acm.fzu.edu.cn/problem.php?pid=2226
信心题，还说是信心题，题目给的真好。但是一点都不像信心题。
又是一个新的算法，莫队算法
莫队算法是一个用数组就可以轻易实现的神奇数据结构，可以处理一类无修改的离线区间查询问题(PS:暂时还没有遇到莫队解决更新区间查询的问题)
莫队算法可以在O(1)，实现[l, r]到[l, r±1] / [l±1, r]的转移，然后我们就可以对所有查询分sqrt(n)块，把每个查询所在的块号当做第一关键字，右端点作为第二关键字升序排列。
然后进行状态转移即可。
时间复杂度O(n*sqrt(n))：当i与i+1在同一个块内，则L最多移动sqrt(n),R最多移动n，所以复杂度为O(n*sqrt(n)).
当i与i+1不在同一块内，则L最多移动2*sqrt(n),R最多移动n，复杂度为O(n*sqrt(n)).
------罗茜
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<vector> using namespace std;
#define N 1001 #define memset(a,b) memset(a,b,sizeof(a))
vector<int>G[N]; struct node
{
int l,r,id;
}Q[N*];
int n,q,l[N],r[N],ans[N*];
int a[N*]; int cmp(node c,node d)
{
if(c.l!=d.l)
return c.l<d.l;
else
return c.r<d.r;
} void solve()
{
int L=,R=;
for(int i=;i<=q;i++)
{
while(Q[i].l<L)
{
L--;
l[a[L]]--;
}
while(Q[i].l>L)
{
l[a[L]]++;
L++;
}
while(Q[i].r<R)
{
r[a[R]]--;
R--;
}
while(Q[i].r>R)
{
R++;
r[a[R]]++;
} int Max=;
for(int j=;j<=;j++)
{
if(r[j]<=)
continue;
int u=G[j][r[j]];
int v=G[j][l[j]+];
Max=max(Max,G[j][r[j]]-G[j][l[j]+]); }
ans[Q[i].id]=Max;
}
} int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=;i++)
G[i].clear();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
G[a[i]].push_back(i);
} memset(l,-);
memset(r,-); scanf("%d",&q);
for(int i=;i<=q;i++)
{
scanf("%d %d",&Q[i].l,&Q[i].r);
Q[i].id=i;
}
sort(Q+,Q++q,cmp); solve(); for(int i=;i<=q;i++)
{
printf("%d\n",ans[i]);
}
}
return ;
} /*
5
1 1 1 1 1
3
1 5
3 3
2 5 */