题目： 一个长度为 n 的序列，对于每个位置 i 的数 ai 都有一个优美值，其定义是：找到序列中最长的一段 [l,r] ，满足 l≤i≤r，且 [l,r] 中位数为 ai （我们比较序列中两个位置的数的大小时，以数值为第一关键字，下标为第二关键字比较。这样的话 [l,r] 的长度只有可能是奇数），r-l+1 就是 i 的优美值。
接下来有 Q 个询问，每个询问 [l,r] 表示查询区间 [l,r] 内优美值的最大值。
输入格式 第一行输入 n 。 接下来 n 个整数，代表 ai 。 接下来 Q ，代表有 Q 个区间。 接下来 Q 行，每行两个整数 l,r (l≤r)，表示区间的左右端点。
输出格式 对于每个区间的询问，输出答案。
样例数据 输入 8 16 19 7 8 9 11 20 16 8 3 8 1 4 2 3 1 1 5 5 1 2 2 8 7 8 输出 7 3 1 3 5 3 7 3
【数据规模】 对于 30% 的数据，满足：n,Q≤50； 对于 70% 的数据，满足：n,Q≤2000； 对于所有数据，满足 n≤2000；Q≤100000； ai ≤200
分析：这个题n只有2000，预处理每一个数的优美值，复杂度是O( n2 )，这为询问带来了便捷，复杂度是O(Q*询问长度)，于是总共就是O( n2 +Q*询问长度)的，按这个题的意思，直接查询会被卡，建议使用RMQ优化，但是数据出的水，下面我的代码也没被卡掉……以后看到询问次数超级多的首先考虑预处理。
100分代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<algorithm> #include<cctype> #include<iomanip> #include<queue> #include<set> using namespace std; int getint() { int sum=0,f=1; char ch; for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar()); if(ch=='-') { f=-1; ch=getchar(); } for(;ch>='0'&&ch<='9';ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-48; return sum*f; } const int N=2008; int n,a[N],L[2*N],R[2*N],w[N],Q; void init() { for(int i=1;i<=n;++i) { memset(L,-1,sizeof(L));//L下标是(n+多了几个大于n的)或者(n-多了几个小于n的)，存的是最长的这种情况的左半径 L[n]=0;//如果刚好不多不少这个半径正好n是中位数，那么长度最小就是0，这个必须要先赋值，不然要出事 memset(R,-1,sizeof(R)); R[n]=0;//R理解相同，是右半径 int cnt=0; for(int j=i-1;j>=1;--j)//先处理左边 { if(a[j]>a[i]) cnt++;//如果这个数大于ai if(a[j]<=a[i]) cnt--;//如果这个数小于等于ai（注意，还有第二关键字下标，所以左边的和它大小相同的也算作小于它） L[n+cnt]=i-j;//记录长度，因为是从它本身开始向左的，所以每次更新都能更新成更长值 } cnt=0; for(int j=i+1;j<=n;++j)//右边同理，只是大小相同的当做大于它 { if(a[j]>=a[i]) cnt++; if(a[j]<a[i]) cnt--; R[n+cnt]=j-i; } for(int j=1-i;j<=i-1;++j)//因为左边有i-1个数，所以向左最多有i-1个数小于ai，即j最多是-(i-1) if(L[n+j]>=0&&R[n-j]>=0)//判断有没有这种可能（如果值为-1，那么这种情况是不存在的） { w[i]=max(w[i],L[n+j]+1+R[n-j]); } } } int main() { freopen("beautiful.in","r",stdin); freopen("beautiful.out","w",stdout); n=getint(); for(int i=1;i<=n;++i) a[i]=getint(); init(); Q=getint(); while(Q--)//直接查询即可 { int l,r; l=getint();r=getint(); int ans=0; for(int i=l;i<=r;++i) ans=max(ans,w[i]); cout<<ans<<endl; } return 0; }本题结。
