Codeforces 193D Two Segments (线段树)

大家好，欢迎来到IT知识分享网。

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <map> #include <set> #include <algorithm> #include <ctime> #include <cstdlib> #include <functional> #pragma comment(linker,"/STACK:,") using namespace std; #define eps 1e-10 #define N  #define B 20 #define M  #define inf 0x3f3f3f3f #define LL long long #define pii pair<int, int> #define MP make_pair #define fi first #define se second #define mod  #define ls (i << 1) #define rs (ls | 1) #define md (ll + rr >> 1) #define lson ll, md, ls #define rson md + 1, rr, rs int mi1[N << 2], mi2[N << 2], s1[N << 2], s2[N << 2], lazy[N << 2]; int n, a[N], f[N]; void build(int ll, int rr, int i) { mi1[i] = 0, s1[i] = rr - ll + 1; mi2[i] = inf, s2[i] = 0; if(ll == rr) return; build(lson); build(rson); } LL ans; int t; void upd(int v, int i) { mi1[i] += v; mi2[i] += v; lazy[i] += v; } void push_down(int i) { if(lazy[i]) { upd(lazy[i], ls); upd(lazy[i], rs); lazy[i] = 0; } } void calc(int i, int x, int v) { if(v == 0) return; if(x < mi1[i]) { mi2[i] = mi1[i], s2[i] = s1[i]; mi1[i] = x, s1[i] = v; } else if(x == mi1[i]) { s1[i] += v; } else if(x < mi2[i]) { mi2[i] = x, s2[i] = v; } else if(x == mi2[i]) { s2[i] += v; } } void push_up(int i) { mi1[i] = mi1[ls], s1[i] = s1[ls]; mi2[i] = mi2[ls], s2[i] = s2[ls]; calc(i, mi1[rs], s1[rs]); calc(i, mi2[rs], s2[rs]); } void update(int l, int r, int v, int ll, int rr, int i) { if(ll == l && rr == r) { upd(v, i); return; } push_down(i); if(r <= md) update(l, r, v, lson); else if(l > md) update(l, r, v, rson); else { update(l, md, v, lson); update(md + 1, r, v, rson); } push_up(i); } void query(int l, int r, int ll, int rr, int i) { if(ll == l && rr == r) { calc(t, mi1[i], s1[i]); calc(t, mi2[i], s2[i]); return; } push_down(i); if(r <= md) query(l, r, lson); else if(l > md) query(l, r, rson); else { query(l, md, lson); query(md + 1, r, rson); } } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); f[a[i]] = i; } build(1, n, 1); ans = 0; t = (N << 2) - 1; for(int i = 1; i <= n; ++i) { int l = -1, r = -1; if(f[i] > 1 && a[f[i] - 1] <= i) l = a[f[i] - 1]; if(f[i] < n && a[f[i] + 1] <= i) r = a[f[i] + 1]; if(l > r) swap(l, r); if(r == -1) update(1, i, 1, 1, n, 1); else if(l == -1) { update(r + 1, i, 1, 1, n, 1); } else { update(r + 1, i, 1, 1, n, 1); update(1, l, -1, 1, n, 1); } mi1[t] = inf, mi2[t] = inf; query(1, i, 1, n, 1); if(mi1[t] == 1) ans += s1[t]; if(mi2[t] == 2) ans += s2[t]; } printf("%lld\n", ans - n); return 0; }