線段樹..
有個小地方寫次了..wa了好幾次..
寫了這道題..才感覺自己終于知道線段樹是個什么東西了..囧
#include <iostream>
using namespace std;
const int MAXN=100002;
struct node
{
int l,r;
int lnum,rnum;
int t;
}tree[MAXN*3];
int N,M;
int C[MAXN];
void make_tree(int l,int r,int p)
{
if (l==r)
{
tree[p].l=l;
tree[p].r=r;
tree[p].lnum=1;
tree[p].rnum=1;
tree[p].t=1;
return;
}
int mid=(l+r)/2;
make_tree(l,mid,p*2);
make_tree(mid+1,r,p*2+1);
int ls=p*2,rs=p*2+1;
tree[p].l=l;
tree[p].r=r;
tree[p].lnum=tree[ls].lnum;
if (C[tree[ls].r]==C[tree[rs].l]&&tree[p].lnum==mid-l+1) tree[p].lnum+=tree[rs].lnum;
tree[p].rnum=tree[rs].rnum;
if (C[tree[rs].l]==C[tree[ls].r]&&tree[p].rnum==r-mid) tree[p].rnum+=tree[ls].rnum;
tree[p].t=max(tree[ls].t,tree[rs].t);
tree[p].t=max(tree[p].t,tree[p].rnum);
tree[p].t=max(tree[p].t,tree[p].lnum);
if (C[tree[ls].r]==C[tree[rs].l]) tree[p].t=max(tree[p].t,tree[ls].rnum+tree[rs].lnum);
}
bool nnew;
int nl,nr,nlnum,nrnum,nt;
void find(int l,int r,int p)
{
int count=0;
int ll=tree[p].l,rr=tree[p].r;
if (ll>=l&&rr<=r)
{
if (!nnew)
{
nl=tree[p].l;
nr=tree[p].r;
nlnum=tree[p].lnum;
nrnum=tree[p].rnum;
nt=tree[p].t;
nnew=true;
return;
}
else
{
if (C[nr]==C[tree[p].l]) nt=max(nt,nrnum+tree[p].lnum);
if (C[nr]==C[tree[p].l]&&nlnum==nr-nl+1) nlnum+=tree[p].lnum;
if (C[nr]==C[tree[p].l]&&tree[p].rnum==tree[p].r-tree[p].l+1) nrnum+=tree[p].rnum; else nrnum=tree[p].rnum;
nt=max(nt,tree[p].t);
nt=max(nt,nlnum);
nt=max(nt,nrnum);
nr=tree[p].r;
}
return;
}
int mid=(ll+rr)/2;
if (l<=mid) find(l,r,p*2);
if (r>mid) find(l,r,p*2+1);
}
int main()
{
while(1)
{
scanf("%d",&N);
if (N==0) break;
scanf("%d",&M);
for (int i=1;i<=N;i++)
scanf("%d",&C[i]);
make_tree(1,N,1);
for (int i=1;i<=M;i++)
{
int x,y;
scanf("%d%d",&x,&y);
nnew=false;
nt=0;
find(x,y,1);
printf("%d\n",nt);
}
}
return 0;
}