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

Problem - E - Codeforces

题意：

思路：

感觉是个套路题

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

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

Code：

#include <bits/stdc++.h>#define int long longusing 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;
}