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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
const int N = 300000 + 10;
vector<pii> v;
int n, f[N], son[N][2], tmp[N], a[N];
ll R[N];
bool rev[N];
bool isroot(int x) { return !f[x] || son[f[x]][0] != x && son[f[x]][1] != x; }
void rev1(int x) {
if (!x) return;
swap(son[x][0], son[x][1]);
rev[x] ^= 1;
}
void pb(int x) {
if (rev[x]) rev1(son[x][0]), rev1(son[x][1]), rev[x] = 0;
}
void rotate(int x) {
int y = f[x], w = son[y][1] == x;
son[y][w] = son[x][w ^ 1];
if (son[x][w ^ 1]) f[son[x][w ^ 1]] = y;
if (f[y]) {
int z = f[y];
if (son[z][0] == y)
son[z][0] = x;
else if (son[z][1] == y)
son[z][1] = x;
}
f[x] = f[y];
f[y] = x;
son[x][w ^ 1] = y;
}
void splay(int x) {
int s = 1, i = x, y;
tmp[1] = i;
while (!isroot(i)) tmp[++s] = i = f[i];
while (s) pb(tmp[s--]);
while (!isroot(x)) {
y = f[x];
if (!isroot(y)) {
if ((son[f[y]][0] == y) ^ (son[y][0] == x))
rotate(x);
else
rotate(y);
}
rotate(x);
}
}
void access(int x) {
for (int y = 0; x; y = x, x = f[x]) splay(x), son[x][1] = y;
}
int root(int x) {
access(x);
splay(x);
while (son[x][0]) x = son[x][0];
return x;
}
void makeroot(int x) {
access(x);
splay(x);
rev1(x);
}
void link(int x, int y) {
makeroot(x);
f[x] = y;
access(x);
}
void cutf(int x) {
access(x);
splay(x);
f[son[x][0]] = 0;
son[x][0] = 0;
}
void cut(int x, int y) {
makeroot(x);
cutf(y);
}
void init() {
memset(f, 0, sizeof(f));
memset(son, 0, sizeof(son));
memset(rev, 0, sizeof(rev));
memset(R, 0, sizeof(R));
}
vector<int> t;
int findx(int p) { return lower_bound(all(t), p) - begin(t) + 1; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), t.pb(a[i]);
sort(all(t));
t.erase(unique(all(t)), end(t));
int r = 1;
ll ans = 0;
for (int l = 1; l <= n; l += 2) {
r = max(l, r);
while (r + 2 <= n && root(findx(a[r + 1])) != root(findx(a[r + 2]))) {
link(findx(a[r + 1]), findx(a[r + 2]));
r += 2;
}
if (r - l >= 2 * a[l]) v.push_back({l, l + 2 * a[l]});
if (a[l + 1] != a[l + 2]) cut(findx(a[l + 1]), findx(a[l + 2]));
}
init();
r = 2;
for (int l = 2; l <= n; l += 2) {
r = max(l, r);
while (r + 2 <= n && root(findx(a[r + 1])) != root(findx(a[r + 2]))) {
link(findx(a[r + 1]), findx(a[r + 2]));
r += 2;
}
if (r - l >= 2 * a[l]) v.push_back({l, l + 2 * a[l]});
if (a[l + 1] != a[l + 2]) cut(findx(a[l + 1]), findx(a[l + 2]));
}
sort(all(v));
for (auto &i : v) {
R[i.second] += R[i.first - 1] + 1;
ans += R[i.first - 1] + 1;
}
printf("%lld\n", ans);
return 0;
}
|
