1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
| #include <bits/stdc++.h> typedef long long LL; const int N = 200000 + 5;
int n, a[N], b[N], max[N << 2], lazy[N << 2], nxt[N]; LL sum[N << 2];
std::map<int, int> vis;
void pushup(int now) { sum[now] = sum[now << 1] + sum[now << 1 | 1]; max[now] = std::max(max[now << 1], max[now << 1 | 1]); }
void Build(int now, int l, int r) { lazy[now] = -1; if (l == r) { sum[now] = max[now] = b[l]; return; } int mid = (l + r) >> 1; Build(now << 1, l, mid); Build(now << 1 | 1, mid + 1, r); pushup(now); }
void pushdown(int now, int l, int r) { if (lazy[now] != -1) { int mid = (l + r) >> 1; max[now << 1] = max[now << 1 | 1] = lazy[now]; sum[now << 1] = 1LL * (mid - l + 1) * lazy[now]; sum[now << 1 | 1] = 1LL * (r - mid) * lazy[now]; lazy[now << 1] = lazy[now << 1 | 1] = lazy[now]; lazy[now] = -1; } }
void Add(int now, int l, int r, int al, int ar, int delta) { if (al > r || ar < l) return; else if (al <= l && ar >= r) { max[now] = delta; sum[now] = 1LL * (r - l + 1) * delta; lazy[now] = delta; return; } pushdown(now, l, r); int mid = (l + r) >> 1; if (al <= mid) Add(now << 1, l, mid, al, ar, delta); if (ar > mid) Add(now << 1 | 1, mid + 1, r, al, ar, delta); pushup(now); }
int Find(int now, int l, int r, int k) { if (l == r) return l; pushdown(now, l, r); int mid = (l + r) >> 1; if (max[now << 1] > k) return Find(now << 1, l, mid, k); else return Find(now << 1 | 1, mid + 1, r, k); }
int main() { while (~scanf("%d", &n) && n) { int now = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); vis[a[i]] = 1; while (vis[now]) now++; b[i] = now; } for (int i = 1; i <= n; i++) vis[a[i]] = n + 1; for (int i = n; i >= 1; i--) { nxt[i] = vis[a[i]]; vis[a[i]] = i; } Build(1, 1, n); LL ans = sum[1]; for (int i = 2; i <= n; i++) { Add(1, 1, n, i - 1, i - 1, 0); if (a[i - 1] < max[1]) { int l = Find(1, 1, n, a[i - 1]), r = nxt[i - 1] - 1; if (l <= r) Add(1, 1, n, l, r, a[i - 1]); } ans += sum[1]; } printf("%I64d\n", ans); vis.clear(); memset(nxt, 0, sizeof(nxt)); } return 0; }
|