第一步先莫队分块。
对于每一块l~r，初始右端点设为r+1，然后每个询问先将右端点往右移，然后处理询问在l~r之间的部分，最后用一个栈再把l~r的复原。
具体来说是维护两个数组now1和now2，一个向右最长的长度，一个向左的长度，每插入一个值x，用x+1的now2更新x的now2，用x-1的now1更新x的now1，now1[x]+now2[x]-1可能为最终答案，再把x所在的最长区间的左右端点的now数组更新，中间的值不需要更新，因为不可能再往中间插入数了。
有生以来第一次bzoj榜一。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 50005
#define d 223
using namespace std;
int n,m;
int c[N];
int ans[N];
struct node
{
int l,r,id,yuan;
friend bool operator < (node aa,node bb)
{
if(aa.id!=bb.id)return aa.id<bb.id;
return aa.r<bb.r;
}
}a[N];
int now1[N],now2[N];
int st1[N*],st2[N*],top;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&c[i]);
for(int i=;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].yuan=i;a[i].id=(a[i].l-)/d+;
}
sort(a+,a+m+);
int as=;int r=,t=;
for(int i=;i<=m;i++)
{
if(a[i].id!=a[i-].id)
{
as=;
memset(now1,,sizeof(now1));
memset(now2,,sizeof(now2));
r=t=a[i].id*d;
}
while(a[i].r>r)
{
r++;
now1[c[r]]=now1[c[r]+]+;
now2[c[r]]=now2[c[r]-]+;
int tt=now1[c[r]]+now2[c[r]]-;
now2[c[r]+now1[c[r]]-]=tt;
now1[c[r]-now2[c[r]]+]=tt;
as=max(as,tt);
}
int tmp=as;top=;
for(int j=a[i].l;j<=min(a[i].r,t);j++)
{
now1[c[j]]=now1[c[j]+]+;
now2[c[j]]=now2[c[j]-]+;
int tt=now1[c[j]]+now2[c[j]]-;
int rr=c[j]+now1[c[j]]-;int ll=c[j]-now2[c[j]]+;
st1[++top]=rr;st2[top]=now2[rr];
st1[++top]=ll;st2[top]=now1[ll];
now2[rr]=tt;
now1[ll]=tt;
tmp=max(tmp,tt);
}
for(int j=top;j>=;j--)
{
if(j%==)now1[st1[j]]=st2[j];
else now2[st1[j]]=st2[j];
}
for(int j=a[i].l;j<=min(a[i].r,t);j++)
{
now1[c[j]]=now2[c[j]]=;
}
ans[a[i].yuan]=tmp;
}
for(int i=;i<=m;i++)printf("%d\n",ans[i]);
return ;
}