线段树
代码：
#include#include using namespace std;int n,m;struct e{ int l,r,max,maxl,maxr;};e tree[300001];int b[100001];void build(int s,int t,int p){ int i,j,k; tree[p].l=s; tree[p].r=t; if(s==t) { tree[p].max=tree[p].maxl=tree[p].maxr=1; return; } k=(s+t)>>1; build(s,k,p*2); build(k+1,t,p*2+1); tree[p].maxl=tree[2*p].maxl; if(tree[2*p].maxl==k-s+1&&b[k]==b[k+1]) tree[p].maxl+=tree[2*p+1].maxl; tree[p].maxr=tree[2*p+1].maxr; if(tree[2*p+1].maxr==t-k&&b[k]==b[k+1]) tree[p].maxr+=tree[2*p].maxr; i=0; if(b[k]==b[k+1]) i=tree[2*p].maxr+tree[2*p+1].maxl; j=max(tree[2*p].max,tree[2*p+1].max); tree[p].max=max(i,j);}void find(int s,int t ,int p,int &x,int &y,int &sum){ if(s<=tree[p].l&&tree[p].r<=t) { x=tree[p].maxl; y=tree[p].maxr; sum=tree[p].max; return; } if(t<=tree[2*p].r) find(s,t,p*2,x,y,sum); else if(s>=tree[2*p+1].l) find(s,t,2*p+1,x,y,sum); else { int i,j,k,i1,j1,k1; find(s,t,2*p,i1,j1,k1); find(s,t,2*p+1,i,j,k); int mid=tree[2*p].r; x=i1; if(b[mid]==b[mid+1]&&i1==mid-max(s,tree[p].l)+1) x+=i; y=j; if(b[mid]==b[mid+1]&&j==min(t,tree[p].r)-mid) y+=j1; sum=0; sum=max(k1,k); if(b[mid]==b[mid+1]) sum=max(sum,j1+i); }}void read(){// ifstream cin("in.txt"); int i,j,k,s,t,x,y,sum; while(scanf("%d",&n)!=EOF) { if(n==0) return; scanf("%d",&m); //cin>>m; for(i=1;i<=n;i++) scanf("%d",&b[i]); //cin>>b[i]; build(1,n,1); for(i=1;i<=m;i++) { //cin>>s>>t; scanf("%d%d",&s,&t); find(s,t,1,x,y,sum); cout< <