网站缩略图制作,建设网站需要机房吗,发稿渠道,长沙做网站一般要多少钱Problem - E - Codeforces
题意#xff1a; 思路#xff1a;
感觉是个套路题
对区间计数#xff0c;按照CF惯用套路#xff0c;枚举其中一个端点#xff0c;对另一个端点计数
对于这道题#xff0c;枚举右端点#xff0c;对左端点计数 Code#xff1a;
#include 思路
感觉是个套路题
对区间计数按照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::stackint 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;
}
