beautiful
2.1 题目描述
一个长度为 n 的序列，对于每个位置 i 的数 ai 都有一个优美值，其定义是：找到序列中最 长的一段 [l, r]，满足 l ≤ i ≤ r，且 [l, r] 中位数为 ai（我们比较序列中两个位置的数的大小时， 以数值为第一关键字，下标为第二关键字比较。这样的话 [l, r] 的长度只有可能是奇数），r - l + 1 就是 i 的优美值。 接下来有 Q 个询问，每个询问 [l, r] 表示查询区间 [l, r] 内优美值的最大值。
2.2 输入
第一行输入 n 接下来 n 个整数，代表 ai 接下来 Q，代表有 Q 个区间接下来 Q 行，每行 两个整数 l, r(l ≤ r)，表示区间的左右端点
2.3 输出
对于每个区间的询问，输出答案
2.4 Sample Input
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
2.5 Sample Output
7
3
1
3
5
3
7
3
3
2.6 数据范围及约定
对于 30% 的数据，满足 n，Q ≤ 50
对于 70% 的数据，满足 n，Q ≤ 2000 对于所有数据，满足 n ≤ 2000, Q ≤ 100000,ai ≤ 200
———————————————分割线———————————————
考试没有理解这道题，导致连暴力都没有写出来，本题直接爆零。
看完标程和解题报告后豁然开朗。
n2 预处理。对于每个数，往左往右各扫一遍，遇到大于它的数则状态 S++，小于则 S--， 由题目定义可知没有相等的。然后记录下每个状态 S 的最长长度，然后枚举左边的状态，找右边的状态，取 max 计算出优美值。 接着就是一个纯 RMQ 的问题了.
#include "cstdio"
#include "cstring"
#include "iostream" using namespace std ;
const int maxN = ;
const int INF = ;
typedef long long QAQ ; int L[ maxN ] , R[ maxN ] , w[ maxN ] , A[ maxN ] ; inline int max ( int x , int y ) { return x < y ? y : x ;} void Init ( int n ) {
for ( int i= ; i<=n ; ++i ) {
memset ( L , , sizeof ( L ) ) ;
memset ( R , , sizeof ( R ) ) ;
L[ n ] = ; R[ n ] = ;
int _cnt = ; for ( int j = i - ; j>= ; --j ) {
if ( A[ j ] > A[ i ] ) ++_cnt ;
else if ( A[ j ] <= A[ i ] ) --_cnt ;
L[ n + _cnt ] = i - j ;
} _cnt = ;
for ( int j = i + ; j <= n ; ++j ) {
if ( A[ j ] >= A[ i ] ) ++_cnt ;
else if ( A[ j ] < A[ i ] ) --_cnt ;
R[ n + _cnt ] = j - i ;
} for ( int j = - i ; j <= i - ; ++j ) {
if ( L[ n + j ] >= && R[ n - j ] >= ) {
w [ i ] = max ( w [ i ] , L[ n + j ] + R[ n - j ] + ) ;
}
}
}
}
int main ( ) {
int N , T , l , r ;
scanf ( "%d" , &N ) ;
for ( int i= ; i<=N ; ++i ) {
scanf ( "%d" , A + i ) ;
}
Init ( N ) ;
scanf ( "%d" , &T ) ;
while ( T-- ) {
QAQ ans = -INF ;
cin >> l >> r ;
for ( int i=l ; i<=r ; ++i ) ans = max ( ans , w[ i ] ) ;
printf ( "%I64d\n" , ans ) ;
}
}
Beauitiful
NOIP_RP++;
2016-10-08 00:18:20
(完)