题解 CF1119A 【Ilya and a Colorful Walk】
皎月半洒花
2019-05-21 17:59:36
好的我是来搞笑的。
众所周知这是一道O(n)好题，但是数据结构学傻了就只会O(nlogn)了。
然后就是线段树贪心
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 500010
#define Inf 0x3f3f3f
using namespace std ; int Ans = 0 ;
int N, S[MAXN << 2], T[MAXN << 2], base[MAXN], Pre[MAXN], End[MAXN] ;
inline void update1(int rt, int l, int r, int pos, int k){
if (l == pos && r == pos) { S[rt] = k ; return ; }
int mid = (l + r) >> 1 ; if (pos <= mid) update1(rt << 1, l, mid, pos, k) ;
else update1(rt << 1 | 1, mid + 1, r, pos, k) ; S[rt] = min(S[rt << 1], S[rt << 1 | 1]) ;
}
inline void update2(int rt, int l, int r, int pos, int k){
if (l == pos && r == pos) { T[rt] = k ; return ; }
int mid = (l + r) >> 1 ; if (pos <= mid) update2(rt << 1, l, mid, pos, k) ;
else update2(rt << 1 | 1, mid + 1, r, pos, k) ; T[rt] = max(T[rt << 1], T[rt << 1 | 1]) ;
}
inline int query1(int rt, int l, int r, int ql, int qr){
if (ql > qr) return Inf ;
if (ql <= l && qr >= r) return S[rt] ; int res = Inf, mid = (l + r) >> 1 ;
if (ql <= mid) res = min(res, query1(rt << 1, l, mid, ql, qr)) ;
if (qr > mid) res = min(res, query1(rt << 1 | 1, mid + 1, r, ql, qr)) ; return res ;
}
inline int query2(int rt, int l, int r, int ql, int qr){
if (ql > qr) return 0 ;
if (ql <= l && qr >= r) return T[rt] ; int res = -1, mid = (l + r) >> 1 ;
if (ql <= mid) res = max(res, query2(rt << 1, l, mid, ql, qr)) ;
if (qr > mid) res = max(res, query2(rt << 1 | 1, mid + 1, r, ql, qr)) ;
return res ;
}
int main(){
cin >> N ; int i ;
memset(S, 63, sizeof(S)) ;
memset(Pre, 63, sizeof(Pre)) ;
memset(End, -1, sizeof(End)) ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
for (i = 1 ; i <= N ; ++ i) if (Pre[base[i]] > i) Pre[base[i]] = i ;
for (i = N ; i >= 1 ; -- i) if (End[base[i]] < i) End[base[i]] = i ;
for (i = 1 ; i <= N ; ++ i) update1(1, 1, N, i, Pre[i]) ;
for (i = 1 ; i <= N ; ++ i)
update2(1, 1, N, i, End[i]) ;
for (i = 1 ; i <= N ; ++ i){
int t1 = min(query1(1, 1, N, 1, base[i] - 1), query1(1, 1, N, base[i] + 1, N)) ;
int t2 = max(query2(1, 1, N, 1, base[i] - 1), query2(1, 1, N, base[i] + 1, N)) ;
Ans = max(Ans, max(i - t1, t2 - i)) ;
}
cout << Ans << endl ; return 0 ;
}
```