Problem - B - Codeforces
求出所有长度x的子段中最小值的最大值
考虑O(n3)暴力的做法,枚举所有长度的子区间找最小值的最大。
这种做法即便是将最小值的查询通过线段树或散列表(ST)降低到log级别也还是有O(n2logn)的复杂度。
考虑另外的做法:
我们可以将区间内最小值转化成最小值所对应的区间。那么,每一种区间长度就都能对应一个最小值的最大值。所以我们可以维护一个mi数组。$mi_i$表示最大长度为i的区间内的最小值的最大值。
int n , m , k ; ll a[N] ; ll mi[N] ;//长度为i的子段的最小值 int lb[N] ; int rb[N] ; struct Node{ int l , r ; ll mx ; }tr[N << 2] ; void pushup(int now){ tr[now].mx = max(tr[now << 1].mx , tr[now << 1 | 1].mx) ; } void build(int now , int l , int r){ tr[now] = {l , r , -INF} ; if(l == r){ tr[now].mx = mi[l] ; return ; } int mid = l + r >> 1 ; build(now << 1 , l , mid) ; build(now << 1 | 1 , mid + 1 , r) ; pushup(now) ; } ll query(int now , int l , int r){ if(l <= tr[now].l && tr[now].r <= r) return tr[now].mx ; int mid = tr[now].l + tr[now].r >> 1 ; ll res = -INF ; if(l <= mid) res = max(res , query(now << 1 , l , r)) ; if(mid < r ) res = max(res , query(now << 1 | 1 , l , r)) ; return res ; } void solve(){ cin >> n ; rep(i , 1 , n) cin >> a[i] ; a[0] = a[n + 1] = -1 ; stack<ll> stk ; rep(i , 1 , n + 1){ while(stk.size() && a[stk.top()] > a[i]){ rb[stk.top()] = i ; stk.pop() ; }stk.push(i) ; } while(stk.size()) stk.pop() ; drep(i , 0 , n){ while(stk.size() && a[i] < a[stk.top()]){ lb[stk.top()] = i ; stk.pop() ; }stk.push(i) ; } //找到每一个ai作为最小值的区间 [lb+1,rb-1] rep(i , 1 , n){ ll ln = rb[i] - 1 - (lb[i] + 1) + 1 ; mi[ln] = max(mi[ln] , a[i]) ; } build(1 , 1 , n) ; rep(i , 1 , n){ cout << query(1 , i , n) << " \n"[i ==n] ; } }//code_by_tyrii