首页 > 其他分享 >两个单调栈的问题

两个单调栈的问题

时间:2023-01-30 12:24:12浏览次数:59  
标签:两个 int max stk 问题 -- while vector 单调

两个单调栈的问题

写灵神每日,遇到两个单调栈的经典问题,就放一起了

问题一

https://codeforces.com/problemset/problem/1691/D

输入 t(≤1e5) 表示 t 组数据,每组数据输入 n(≤2e5) 和长为 n 的数组 a (-1e9≤a[i]≤1e9)。所有数据的 n 之和不超过 2e5。

请你判断,对数组 a 的每个非空子数组 b,是否都有 max(b) >= sum(b)?
如果是,输出 YES,否则输出 NO。
注:子数组是连续的。

进阶:做到 O(n) 时间复杂度。

Solution

#include <bits/stdc++.h>
#define SZ(x) (int)x.size()
#define rep(i,a,n) for(int i = (a);i <= (n);i++)
#define dec(i,n,a) for(int i = (n);i >= (a);i--)
using namespace std;
using ll = long long;
using PII = pair<int,int>;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int mod = 1e9 + 7;
/* 
max(a) >= sum(a)
对每个a[i] 作为 max
找 [j, i] 中最小的sum(k (j <= k <= i), i), (j 使得j - 1 < 0 or a[j] > a[i])

O(nlogn) 解法:
维护一个前缀和的st表
对每一个i,就是找最大的s[k, i],s[i]是定值,找出统御区间后,对区间做RMQ询问即可

O(n) 解法:
dp思想
维护mxL数组,mxL[i]表示[j,i]的最大sum
在出栈弹出的过程中,mxL[i] = max(mxL[i], mxL[k] + s[k + 1, i])

对维护单调栈过程中“弹出”的小想法:弹出是在对值做“区间合并”的操作
比如,[1,2,3,4,5,2]
当 stack = [1,2,3,4,5] , need add 2
then, stack be like: [1,2]
这个2就存了[2,3,4,5]的信息
[[1],[2],[3],[4],[5]] add [2]
--> [[1],[2,3,4,5,2]] 栈中存的2是这个区间的右端点
于是可以用单调栈去处理一些 consecutive interval problems 最典型的就是 区间最值相关问题
最值的可结合的性质,使得单调栈易于处理该问题 
 */
void solve() { 
    int n; cin >> n;
    vector a(n, 0);
    for (int &i : a) cin >> i;
    
    vector s(n + 1, 0ll);
    for (int i = 0;i < n;i ++) s[i + 1] = s[i] + a[i];

    stack<int> stk;
    vector mxL(n, (ll)1e18);

    for (int i = 0;i < n;i ++) {
        ll mx = a[i];
        while (!stk.empty() and a[stk.top()] <= a[i]) {
            int t = stk.top(); stk.pop();
            mx = max(mx, s[i + 1] - s[t + 1] + mxL[t]);
        }
        mxL[i] = mx;
        stk.push(i);
    }

    while (!stk.empty()) stk.pop();

    vector mxR(n, (ll)1e18);

    for (int i = n - 1;i >= 0;i --) {
        ll mx = a[i];
        while (!stk.empty() and a[stk.top()] <= a[i]) {
            int t = stk.top(); stk.pop();
            mx = max(mx, s[t] - s[i] + mxR[t]);//[i,t-1][t...]
        }
        mxR[i] = mx;
        stk.push(i);
    }

    for (int i = 0;i < n;i ++) {
        if (mxL[i] > a[i] or a[i] < mxR[i]) {
            cout << "NO\n";
            return;
        }
    }
    
    cout << "YES\n";
}
template<typename T> struct ST{
    ST(vector<T> a, int n){ // cope with in [0,n] 
        siz = n;
        maxv.resize(n+1); minv.resize(n+1);
        int t = __lg(n) + 1;
        for(int i= 0;i<=n;i++) maxv[i].resize(t), minv[i].resize(t);
        for(int i = 0; i <= n; i++) maxv[i][0] = minv[i][0] = a[i];
        for(int j = 1; j < t; j++) {
            for(int i = 0; i <= n - (1<<j)+1; i++) {
                maxv[i][j] = max(maxv[i][j-1], maxv[i+(1 << (j-1))][j-1]);
                minv[i][j] = min(minv[i][j-1], minv[i+(1 << (j-1))][j-1]);
            }
        }
    }
    T getmax(int l,int r){
       int k = __lg(r-l+1);
       return max(maxv[l][k],maxv[r-(1<<k)+1][k]);
    }    
    T getmin(int l,int r){
       int k = __lg(r-l+1);
       return min(minv[l][k],minv[r-(1<<k)+1][k]);
    }    
private:
    int siz = 0;
    vector<vector<T>> maxv, minv;
};
void solve2() { 
    int n; cin >> n;
    vector a(n, 0);
    for (int &i : a) cin >> i;
    
    vector s(n + 1, 0ll);
    for (int i = 0;i < n;i ++) s[i + 1] = s[i] + a[i];

    ST<ll> stt(s, n);

    stack<int> stk;

    for (int i = 0;i < n;i ++) {
        int l = i;
        while (!stk.empty() and a[stk.top()] <= a[i]) {
            int t = stk.top(); stk.pop();
            l = min(t, l);
        }
        // s[i + 1] - min(s[l, i])
        if (s[i + 1] - stt.getmin(l, i) > a[i]) {
            cout << "NO\n";
            return;
        } 
        stk.push(i);
    }

    while (!stk.empty()) stk.pop();

    for (int i = n - 1;i >= 0;i --) {
        int r = i;
        while (!stk.empty() and a[stk.top()] <= a[i]) {
            int t = stk.top(); stk.pop();
            r = max(t, r);
        }
        if (stt.getmax(i + 1, r + 1) - s[i] > a[i]) {
            cout << "NO\n";
            return;
        }
        stk.push(i);
    }

    cout << "YES\n";
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int T; cin>>T;
    while(T--)
        solve2();
    return 0;
}

问题二

https://codeforces.com/contest/1359/problem/D

输入 n(1≤n≤1e5) 和长为 n 的数组 a(-30≤a[i]≤30)。
设 b 为 a 的一个非空连续子数组。
输出 sum(b)-max(b) 的最大值。

(Solution)[https://codeforces.com/contest/1359/submission/191094789]

#include <bits/stdc++.h>
#define SZ(x) (int)x.size()
#define rep(i,a,n) for(int i = (a);i <= (n);i++)
#define dec(i,n,a) for(int i = (n);i >= (a);i--)
using namespace std;
using ll = long long;
using PII = pair<int,int>;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int mod = 1e9 + 7;
/* 
输入 n(1≤n≤1e5) 和长为 n 的数组 a(-30≤a[i]≤30)。
设 b 为 a 的一个非空连续子数组。
输出 sum(b)-max(b) 的最大值。
*/
/*
枚举最大值,对每种情况求一个最大子段和。
答案就是每种情况下最大子段和-max,中取最大。

被卡住的点:
当确定最大值max,求取一个最大子段和s,其框定[l,r]区间可能并不会将max框住
比如 [2,2,2,-10,5]
当max=5,s在[1,3]时取到,这种情况下是不合法的。
但进一步想,这会使得答案错误吗?
取[1,3]时-2是正解,这已经被枚举过。
当max=5枚举出[1,3]再-5,是非法解,但显然非法解不会使得答案更优,也就是不会影响正解
因此,虽然求最大子段和时会枚举到许多非法状态,但不会对答案造成影响。
*/
void solve() { 
    int n; cin >> n;
    vector a(n + 1, 0);
    for (int i = 1;i <= n;i ++) cin >> a[i];

    int mp[61] = {}, B = 30;
    for (int i = 1;i <= n;i ++) mp[a[i] + B] ++;

    int ans = 0;

    for (int i = -30;i <= 30;i ++) if (mp[i + B]) {
        int t = -1e9, curans = 0;
        for (int j = 1;j <= n;j ++) {
            if (a[j] > i) {
                t = -1e9;
            } else {
                if (t < 0) t = a[j];
                else t += a[j];
            }
            // cout << t << ' ' << i << '\n';
            curans = max(t - i, curans);
        }
        ans = max(ans, curans);
    }

    cout << ans;
}
/* 
O(n)做法 适用于值域很大的情况
做单调栈,在维护单调栈过程中维护mxL,mxR数组
mxL:[t,i]区间内最大的区间和
t:以a[i]为max value的区间左端点

维护办法:
mxL[i] = max(mxL[i], presum[j + 1, i] + mxL[j])
dp思想。 因为a[j] <= a[i] 所以mxL[j]一定可以被mxL[i]继承
用 presum[j+1,i]这段区间和+被继承过来的mxL[j] 就是转移
这和区间分段类型的dp f[i] = max(f[i], f[j] + cost(j + 1, i)) 是非常类似的

对mxR的维护同理

最好答案就是 mxL[i] + mxR[i] - 2 * a[i] 的最大值
 */
void solve2() {
    int n; cin >> n;
    vector a(n, 0), s(n + 1, 0);
    for (int &i : a) cin >> i;
    
    for (int i = 0;i < n;i ++) {// [0, i)   sum[l, r] = s[r + 1] - s[l]
        s[i + 1] = s[i] + a[i];
    }

    stack<int> stk;
    vector mxL(n + 1, 0), mxR(n + 1, 0);

    for (int i = 0;i < n;i ++) {
        int mx = a[i];// [1, i] maxpresum
        while (!stk.empty() and a[stk.top()] <= a[i]) {
            int t = stk.top(); stk.pop();
            int prev = s[i + 1] - s[t + 1];// [t + 1, i]
            mx = max(mx, prev + mxL[t]);//  [expend interval][prev]
        }
        mxL[i] = mx; // [0, i] max presum, including a[i]

        stk.push(i);
    }

    while (!stk.empty()) stk.pop();

    for (int i = n - 1;i >= 0;i --) {
        int mx = a[i];
        while (!stk.empty() and a[stk.top()] <= a[i]) {
            int t = stk.top(); stk.pop();
            int sufv = s[t] - s[i];// [i, ... t - 1]
            mx = max(mx, sufv + mxR[t]);
        }
        mxR[i] = mx;
        stk.push(i);
    }

    int ans = 0;
    
    for (int i = 0;i < n;i ++) {
        ans = max(ans, mxL[i] + mxR[i] - 2 * a[i]);
    }

    cout << ans;

}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    //int T; cin>>T;
    //while(T--)
        solve2();
    return 0;
}

标签:两个,int,max,stk,问题,--,while,vector,单调
From: https://www.cnblogs.com/Mxrush/p/17075094.html

相关文章