用的是RMQ 所有可以想到的测试点都对 可提交上去就是WA啊。。
#include <iostream>
#include <cstdio>
using namespace std;
int lg2(int x)
{
	if(x==0)return 0;
	int res=0;
	while(x!=1){x=(x>>1);res++;}
	return res;
}
int dp[400001][18];
int dp1[400001];
int dp2[400001];
int data[400001];
int pow2[18]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
	
	while(true){
		memset(dp,0,sizeof(dp));
		memset(dp1,0,sizeof(dp1));
		memset(dp2,0,sizeof(dp2));
		for(int i=0;i<400001;i++)
			data[i]=10000000;

		int n,q;
		cin>>n;
		if(n==0)return 0;
		cin>>q;
		for(int i=0;i<n;i++)
			scanf("%d",&data[i]);
		for(int i=0;i<n;i++)
		{
			dp[i][0]=1;
			if(i!=0)dp1[i]=(data[i]==data[i-1]?dp1[i-1]+1:0);
			if(i!=0)dp2[n-i-1]=(data[n-i-1]==data[n-i]?dp2[n-i]+1:0);
		}
		for(int i=0;i<n;i++)
			for(int j=1;j<18;j++)
			{
				
				dp[i][j]=max(dp[i][j-1],dp[i+pow2[j-1]][j-1]);
				dp[i][j]=max(dp[i][j],(dp1[i+pow2[j-1]]>pow2[j-1]?pow2[j-1]:dp1[i+pow2[j-1]])+(dp2[i+pow2[j-1]]>=pow2[j-1]?pow2[j-1]-1:dp2[i+pow2[j-1]])+1);
			}
		int x,y;
		for(int i=0;i<q;i++)
		{
			scanf("%d%d",&x,&y);
			x--;y--;
			int lg=lg2(y-x+1);
			int mx=(dp1[x+pow2[lg]-1]>=pow2[lg]?(pow2[lg]-1):dp1[x+pow2[lg]-1])+(dp2[x+pow2[lg]-1]>=(y-x-pow2[lg]+1)?(y-x-pow2[lg]+1):dp2[x+pow2[lg]-1])+1;
			int mx2=(dp1[y-pow2[lg]+1]>=(y-x-pow2[lg]+1)?(y-x-pow2[lg]+1):dp1[y-pow2[lg]+1])+(dp2[y-pow2[lg]+1]>=pow2[lg]?(pow2[lg]-1):dp2[y-pow2[lg]+1])+1;
			printf("%d\n",max(max(dp[x][lg],dp[y-pow2[lg]+1][lg]),max(mx,mx2)));
		}
	}
}