【枚举区间+线段树】CF Ehu 152 E

深碍√TFBOYSˉ_ 2024-03-26 22:39 66阅读 0赞

[Problem - E - Codeforces][]

题意：

![6188f0f0fb3f4bf69d4393c0646a3e16.png][]

思路：

感觉是个套路题

对区间计数，按照CF惯用套路，枚举其中一个端点，对另一个端点计数

对于这道题，枚举右端点，对左端点计数

![b3fac70a4f494c3d8088e0c7946b187a.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 1e6 + 10;
    constexpr int M = 1e6 + 10;
    constexpr int P = 2600;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    struct Segtree {
        int val, lazy;
    }tr[N << 2];
    
    int n;
    int a[N];
    int lmi[N], lmx[N];
    
    void pushup(int rt) {
        tr[rt].val = tr[rt << 1].val + tr[rt << 1 | 1].val;
    }
    void build(int rt, int l, int r) {
        if (l == r) {
            tr[rt].val = 0;
            tr[rt].lazy = -1;
            return;
        }
        int mid = l + r >> 1;
        build(rt << 1, l, mid);
        build(rt << 1 | 1, mid + 1, r);
        pushup(rt);
    }
    void pushdown(int rt, int tot) {
            tr[rt << 1].lazy = tr[rt].lazy;
            tr[rt << 1 | 1].lazy = tr[rt].lazy;
            tr[rt << 1].val = (tot - tot / 2) * (tr[rt].lazy? 1 : 0);
            tr[rt << 1 | 1].val = (tot / 2) * (tr[rt].lazy? 1 : 0);
            tr[rt].lazy = -1;
    }
    void modify(int rt, int l, int r, int x, int y, int k) {
        if (x <= l && r <= y) {
            tr[rt].lazy = k;
            tr[rt].val = k * (r - l + 1);
            return;
        }
        if (tr[rt].lazy != -1) pushdown(rt, r - l + 1);
        int mid = l + r >> 1;
        if (x <= mid) modify(rt << 1, l, mid, x, y, k);
        if (y > mid) modify(rt << 1 | 1, mid + 1, r, x, y, k);
        pushup(rt);
    }
    void solve() {
        std::cin >> n;
        for (int i = 1; i <= n; i ++) {
            std::cin >> a[i];
        }
    
        std::stack<int> S, S2;
        for (int i = 1; i <= n; i ++) {
            while(!S.empty() && a[S.top()] >= a[i]) S.pop();
            lmi[i] = S.empty() ? 0 : S.top();
            S.push(i);
        }
    
        for (int i = 1; i <= n; i ++) {
            while(!S2.empty() && a[S2.top()] <= a[i]) S2.pop();
            lmx[i] = S2.empty() ? 0 : S2.top();
            S2.push(i);
        }
    
        build(1, 1, n);
    
        int ans = 0;
        for (int r = 1; r <= n; r ++) {
            if (lmi[r] + 1 <= r - 1) modify(1, 1, n, lmi[r] + 1, r - 1, 0);
            if (lmx[r] + 1 <= r - 1) modify(1, 1, n, lmx[r] + 1, r - 1, 1);
            ans += tr[1].val;
        }
    
        std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1849/problem/E
[6188f0f0fb3f4bf69d4393c0646a3e16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/036be00baddb4c6cb65f6b55f9f20a3f.png
[b3fac70a4f494c3d8088e0c7946b187a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/14db29882d9043459d272e8b1d73140f.png