T30102: 完美交易窗口

monotonic stack, http://cs101.openjudge.cn/practice/T30102/

【江昊中数学科学学院】思路：对于每个元素, 最大的左边界 l 是上一个大于等于它的元素的下一位, 所以维护一个递减的单调栈 st , 购入点是左边界 l 到当前元素的最右侧的最小值, 因此我还需维护一个严格单调递减的单调栈 purchase , 它保存的是从右往左看的第一个严格最小值. 为了让区间长度最大, 我们每次找购入点都只要找 purchase 里第一个大于等于左边界 l 的位置

c++

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    int max_len = 0;
    stack<int> st;
    vector<int> purchase;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && h[i] > h[st.top()]) {
            st.pop();
        }
        
        int l = (st.empty()) ? 0 : st.top() + 1;
        for (int j = 0; j < purchase.size(); j++) {
            if (purchase[j] >= l) {
                max_len = max(max_len, i - purchase[j] + 1);
            }
        }
        
        while (!purchase.empty() && h[i] <= h[purchase.back()]) {
            purchase.pop_back();
        }
        purchase.push_back(i);

        st.push(i);
    }
    cout << max_len << endl;
    return 0;
}

【黄宇曦地球与空间科学学院】思路：叽里咕噜说什么呢，线段树秒了。

首先考察到连续的一段肯定去思考用单调栈。假定我们通过单调栈得知了 $a_{p}$ 右侧第一个小于等于 $a_{p}$ 的位置 $p^{'}$ ，那么我们在这一段里面，以 $p$ 为左端点的最长区间肯定就是 $[p, p^{'})$ 里面的所有最大值（若有多个）第一个出现的地方。考场上我想到这里就没想了于是首先敲了个 ST 表没过去。转念一想， $O (n \log n)$ 的内存确实会爆掉。所以转而敲一个线段树只用 $O (n)$ 的空间复杂度就过了。

整个过程的时间复杂度是 $O (n \log n)$ ，瓶颈在于线段树的询问处理。

cpp

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using vi = vector<int>;
using usi = unordered_set<int>;

const int MAXN = 1e6 + 5;

int n;

class SegTree {
    int n;
    vector<i64> s;
    vector<i64> pos;

    inline int lson(int x) { return x << 1; }
    inline int rson(int x) { return x << 1 | 1; }

    void push_up(int p) {
        s[p] = max(s[lson(p)], s[rson(p)]);
        pos[p] = s[lson(p)] >= s[rson(p)] ? pos[lson(p)] : pos[rson(p)];
    }
    void build(int l, int r, int p, const vector<i64> &a) {
        if (l == r) {
            s[p] = a[l];
            pos[p] = l;
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, lson(p), a);
        build(mid + 1, r, rson(p), a);
        push_up(p);
    }
    pii query(int ql, int qr, int l, int r, int p) {
        if (ql <= l && r <= qr) {
            return {pos[p], s[p]};
        }
        int mid = l + r >> 1, ret = 0, val = 0;
        if (ql <= mid)
            tie(ret, val) = query(ql, qr, l, mid, lson(p));
        if (mid < qr) {
            auto [rr, vv] = query(ql, qr, mid + 1, r, rson(p));
            if (vv > val) {
                val = vv;
                ret = rr;
            }
        }
        return {ret, val};
    }

  public:
    SegTree(int n, const vector<i64> &a)
        : n(n), s(n + 2 << 2, 0), pos(n + 2 << 2, 0) {
        build(1, n, 1, a);
    }
    int query(int ql, int qr) { return query(ql, qr, 1, n, 1).first; }
};

int main() {
    cin >> n;
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    SegTree st(n, a);
    stack<int> stk;
    int ans = 0;
    for (int i = 1; i <= n + 1; i++) {
        while (!stk.empty() && a[stk.top()] >= a[i]) {
            int l = stk.top();
            stk.pop();
            int r = st.query(l, i - 1);
            if (a[r] > a[l]) {
                ans = max(ans, r - l + 1);
            }
        }
        stk.push(i);
    }
    cout << ans << '\n';
}

【竺景琦、工学院】思路：单调栈。具体优化过程写在后面了。

python

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(ll i=(l),i##_=(r);i<=i##_;++i)
#define Rep(i,l,r) for(ll i=(l),i##_=(r);i<i##_;++i)
#define FOR(i,l,r) for(ll i=(l),i##_=(r);i>=i##_;--i)

const ll N = 1e6+10;
ll a[N],d[N],m[N];
const ll inf = 2e18;
ll read(){
	char c=getchar();ll v=0;bool f=1;
	for(;'0'>c||c>'9';c=getchar())
	    if(c=='-') f = 0;
	for(;'0'<=c&&c<='9';c=getchar())
	    v = (v<<1)+(v<<3)+(c^48);
	return f?v:-v;
}
int main(){
	
	ll n=read();
	For(i,1,n) a[i]=read();
	
	ll dn = 0,now = 0,ans = 0;
	a[0] = inf;
	For(i,1,n){
		while(dn!=0&&a[d[dn]]<a[i]){
		    if(a[now]>a[m[dn]]) now = m[dn];
			--dn;
		}
		if(now!=0) ans = max(ans,i-now+1);
		if(a[now]>=a[i]) now = i;
		d[++dn] = i;m[dn] = now;
		now = 0;
	}
	
	printf("%lld",ans);
	return 0;
}

cpp

#include <iostream>
#include <vector>
#include <algorithm>

auto main() -> int {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  std::cin >> n;
  std::vector<int> h(n);
  for (auto &v : h)
    std::cin >> v;

  std::vector<int> st_max;
  std::vector<int> st_min;

  int ans = 0;
  for (int j = 0; j < n; ++j) {
    while (!st_max.empty() && h[st_max.back()] < h[j])
      st_max.pop_back();

    int left_border = st_max.empty() ? -1 : st_max.back();

    while (!st_min.empty() && h[st_min.back()] >= h[j])
      st_min.pop_back();

    if (!st_min.empty()) {
      auto it = std::upper_bound(st_min.begin(), st_min.end(), left_border);
      if (it != st_min.end()) {
        int min_l = *it;
        ans = std::max(ans, j - min_l + 1);
      }
    }

    st_max.emplace_back(j);
    st_min.emplace_back(j);
  }

  std::cout << ans << '\n';
}

T30102: 完美交易窗口 ​

T30102: 完美交易窗口