Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 雁过留声——预处理+RMQ

Posted by fanhqme at 2009-11-28 18:47:40 on Problem 3419
```首先，可以很快速的获得以每个数i为左端点，区间的最右断点R[i]，

f(i)=min{R[i]-i+1,r-i+1}，

R[i]为单调的

for l<=i<=x f(i)=R[i]-i+1
for x<i<r f(i)=r-i+1

struct BIT{
int d[NMax];
BIT(){for (int i=0;i<NMax;i++)d[i]=0;}
void ins(int a,int x){
for (d[a]=(d[a]<x?x:d[a]);a<N;a+=((a+1)&-(a+1)))
if (d[a]<x)d[a]=x;
}
int ret;
for (ret=0;e>=0 && e-((e+1)&-(e+1))+1>=b;e-=((e+1)&-(e+1)))
if (ret<d[e])ret=d[e];
return ret;
}
}bit;
struct BIA{
int d[NMax];
BIA(){for (int i=0;i<NMax;i++)d[i]=0;}
void ins(int a,int x){if (!a)return;
for (d[a]=(d[a]<x?x:d[a]);a>0;a-=(a&-a))
if (d[a]<x)d[a]=x;
}
int ask(int b,int e){if (!b)b++;if (b>e)return 0;
int ret;
for (ret=0;b<N && b+(b&-b)-1<=e;b+=(b&-b))
if (ret<d[b])ret=d[b];
return ret;
}
}bia;
if (ret>tmp)return ret;
return tmp;
}
for (int i=0;i<2000001;i++)last[i]=N;
R[N-1]=N-1;
last[A[N-1]+1000000]=N-1;
for (int i=N-2;i>=0;i--){
R[i]=R[i+1];
if (last[A[i]+1000000]-1<R[i])R[i]=last[A[i]+1000000]-1;
last[A[i]+1000000]=i;
}
for (int i=0;i<N;i++){
bit.ins(i,R[i]-i+1);
bia.ins(i,R[i]-i+1);
}

if (R[b]>=e)printf("%d\n",e-b+1);
else{
//find that R[l]<e
l=b;r=e;
while (r-l>1){
if (R[(r+l)>>1]<e)l=((r+l)>>1);
else r=((r+l)>>1);
}
if (ret<e-l)ret=e-l;
printf("%d\n",ret);
}
```

Followed by: