-
Notifications
You must be signed in to change notification settings - Fork 0
/
C.cpp
112 lines (84 loc) · 2.15 KB
/
C.cpp
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll tree[400009], lazy[400009], last[100009], ans[100009], ara[100009];
struct query {
ll l, r, id;
} qry[100009];
bool cmp(query a, query b)
{
return a.r < b.r;
}
void prop(ll lo, ll hi, ll node)
{
if(lo == hi)
return;
tree[2 * node] += lazy[node];
tree[2 * node + 1] += lazy[node];
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
lazy[node] = 0;
}
void update(ll lo, ll hi, ll left, ll right, ll node)
{
if(lazy[node]) prop(lo, hi, node);
if(lo > right || hi < left)
return;
if(lo >= left && hi <= right) {
tree[node]++;
lazy[node]++;
return;
}
ll mid = (lo + hi) / 2;
update(lo, mid, left, right, 2 * node);
update(mid + 1, hi, left, right, 2 * node + 1);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
ll query(ll lo, ll hi, ll left, ll right, ll node)
{
if(lazy[node]) prop(lo, hi, node);
if(lo > right || hi < left)
return 0;
if(lo >= left && hi <= right)
return tree[node];
ll mid = (lo + hi) / 2;
ll p1 = query(lo, mid, left, right, 2 * node);
ll p2 = query(mid + 1, hi, left, right, 2 * node + 1);
return max(p1, p2);
}
bool mark[100009];
int main()
{
ll n;
cin >> n;
for(ll i = 1; i <= n; i++)
scanf("%lld", &ara[i]);
for(ll i = 1; i < n; i++)
{
qry[i].l = i + 1, qry[i].r = n;
qry[i].id = i;
}
//sort(qry + 1, qry + q + 1, cmp);
ll indx = 1, me = 0;
for(ll i = 1; i <= n; i++)
{
update(1, n, last[ ara[i] ] + 1, i, 1);
last[ ara[i] ] = i;
while(indx <= n && qry[indx].r == i)
{
ans[ qry[indx].id ] = query(1, n, qry[indx].l, qry[indx].r, 1);
ll tmpa = ans[ qry[indx].id ];
ll left = qry[indx].l - 1;
if(mark[ ara[left] ] == 1) {
indx++;
continue;
}
mark[ ara[left] ] = 1;
//cout << left << " " << ara[left] << endl;
me += tmpa;
indx++;
}
}
cout << me << endl;
return 0;
}