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
| #include <bits/stdc++.h>
#define Val first
#define Pos second
#define LS (X << 1)
#define RS (X << 1 | 1)
#define Mid ((L + R) >> 1)
#define Node(X, Y) make_pair(X, Y)
using namespace std;
typedef long long ll;
const int Maxn = 1e5 + 10, Mod = 1e9 + 7;
int N, M, Last[Maxn], Now[Maxn];
int A[Maxn], B[Maxn];
ll Ans;
int Min[Maxn << 2], Cnt[Maxn << 2], Tag[Maxn << 2];
inline void PushUp(int X)
{
Min[X] = min(Min[LS], Min[RS]), Cnt[X] = 0;
if (Min[X] == Min[LS]) Cnt[X] += Cnt[LS];
if (Min[X] == Min[RS]) Cnt[X] += Cnt[RS];
}
inline void F(int X, int V)
{
Min[X] += V;
Tag[X] += V;
}
inline void PushDown(int X)
{
if (!Tag[X]) return ;
F(LS, Tag[X]), F(RS, Tag[X]);
Tag[X] = 0;
}
void Build(int L, int R, int X = 1)
{
if (L == R)
{
Min[X] = 0, Cnt[X] = 1;
return;
}
Build(L, Mid, LS);
Build(Mid + 1, R, RS);
}
inline void UpDate(int L, int R, int Tl, int Tr, int V, int X = 1)
{
if (L >= Tl && R <= Tr)
{
F(X, V) ;
return ;
}
PushDown(X);
if (Tl <= Mid) UpDate (L, Mid, Tl, Tr, V, LS);
if (Tr > Mid) UpDate (Mid + 1, R, Tl, Tr, V, RS);
PushUp(X);
}
int Query(int L, int R, int Tl, int Tr, int X = 1)
{
if (L >= Tl && R <= Tr)
{
if (Min[X] == -1) return Cnt[X];
else return 0;
}
int Ans(0); PushDown(X);
if (Tl <= Mid) Ans += Query (L, Mid, Tl, Tr, LS);
if (Tr > Mid) Ans += Query (Mid + 1, R, Tl, Tr, RS);
return Ans;
}
stack <pair <int, int> > Gtr, Les;
int main()
{
scanf ("%d", &N);
for (int i = 1; i <= N; ++i) scanf ("%d", A + i), B[i] = A[i];
sort (B + 1, B + N + 1);
M = unique (B + 1, B + N + 1) - B - 1;
for (int i = 1; i <= N; ++i)
{
int Temp = lower_bound(B + 1, B + M + 1, A[i]) - B;
Last[i] = Now[Temp], Now[Temp] = i;
}
Build(1, N);
Gtr.push(Node(0, 0)), Les.push(Node(Mod, 0));
for (int i = 1; i <= N; ++i)
{
while (Les.size() && Les.top().Val <= A[i])
{
pair <int, int> Top = Les.top(); Les.pop();
UpDate(1, N, Les.top().Pos + 1, Top.Pos, A[i] - Top.Val);
}
Les.push(Node(A[i], i));
while (Gtr.size() && Gtr.top().Val >= A[i])
{
pair <int, int> Top = Gtr.top(); Gtr.pop();
UpDate(1, N, Gtr.top().Pos + 1, Top.Pos, Top.Val - A[i]);
}
Gtr.push(Node(A[i], i));
UpDate(1, N, Last[i] + 1, i, -1);
Ans += Query(1, N, 1, i);
}
printf ("%lld\n", Ans);
}
|