本文共 1660 字，大约阅读时间需要 5 分钟。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=100000; int min(int a,int b) { return a>b?b:a;}; int max(int a,int b) { return a>b?a:b;}; int lef[big+5],righ[big+5]; int a[big+5],p[big+5],q[big+5],data[4*big+5],v[big+5]; struct Node{ int lp;int rp; }kind[big+5]; void build(int n,int l,int r) { if(r-l==1) { data[n]=kind[l].rp-kind[l].lp+1; return; } build(2*n+1,l,(l+r)>>1); build(2*n+2,(l+r)>>1,r); data[n]=max(data[2*n+1],data[2*n+2]); } int query(int a,int b,int k,int l,int r) { if(r<=a||l>=b) return -inf; else if(a<=l&&r<=b) return data[k]; else if(r>a&&l >1); int tempr=query(a,b,2*k+2,(l+r)>>1,r); return templ>tempr?templ:tempr; } } int n,c,cnt; void init() { scanf("%d",&c); cnt=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(i==1||a[i]!=a[i-1]) { lef[i]=i; ++cnt; kind[cnt].lp=i; kind[cnt-1].rp=i-1; } else lef[i]=lef[i-1]; v[i]=cnt; } build(0,1,cnt+1); for(int i=n;i>=1;i--) if(i==n||a[i]!=a[i+1]) righ[i]=i; else righ[i]=righ[i+1]; for(int i=1;i<=c;i++) scanf("%d %d",&p[i],&q[i]); } int main() { while(~scanf("%d",&n)&&n) { init(); for(int i=1;i<=c;i++) { int x=p[i],y=q[i]; if(a[x]==a[y]) printf("%d\n",y-x+1); else if(righ[x]+1==lef[y]) printf("%d\n",max(righ[x]-x+1,y-lef[y]+1)); else { int temp=max(righ[x]-x+1,y-lef[y]+1); printf("%d\n",max(temp,query(v[x]+1,v[y],0,1,cnt+1))); } } } return 0; }
转载地址：http://mvgsi.baihongyu.com/