beautiful.cpp

【一句话题意】给一个长度为n的序列，第i个数的优美值为包含i且i为中位数的序列的最大长度。有Q个询问，每次询问l到r的区间中的最大优美值。
n<=2e3,Q<=1e5
【分析】先预处理出序列中每个数的优美值，然后构建ST表解决RMQ问题。
预处理与之间的一道标记差值的题目有几分神似，都是用空间换时间。
【code】

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2e3+100;
int n;
int a[maxn],val[maxn],st[maxn][13];
int s[maxn<<1];
inline void read(int &x){
	x=0;int fl=1;char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();
}
inline int rmq(int l,int r){
	int j=0;
	while((1<<j)<=r-l+1) j++;j--;
	return max(st[l][j],st[r-(1<<j)+1][j]);
}
int main(){
	freopen("beautiful.in","r",stdin);
	freopen("beautiful.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
		read(a[i]);
	for(int i=1;i<=n;i++){
		memset(s,-1,sizeof(s));s[maxn]=i;
		int d=0;
		for(int j=i-1;j>=1;j--)
			if(a[j]<=a[i]) d--,s[maxn+d]=j;
			else d++,s[maxn+d]=j;
		d=0,val[i]=i-s[maxn]+1;
		for(int j=i+1;j<=n;j++){
			if(a[i]<=a[j]){d++;if(s[maxn-d]!=-1)val[i]=max(val[i],j-s[maxn-d]+1);}
			else {d--;if(s[maxn-d]!=-1)val[i]=max(val[i],j-s[maxn-d]+1);}
		}
		st[i][0]=val[i];
	}
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
	int l,r,q;
	cin>>q;
	for(int i=1;i<=q;i++){
		read(l),read(r);
		printf("%d\n",rmq(l,r));
	}
	return 0;
}