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
| #define REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100000 + 10;
template <typename T> T read()
{
T ans = 0, p = 1;
char c = getchar();
while (!isdigit(c))
{
if (c == '-') p = -1;
c = getchar();
}
while (isdigit(c))
{
ans = ans * 10 + c - 48;
c = getchar();
}
return ans * p;
}
struct node *null;
const int maxnode = 28000000;
int rt[maxnode], ls[maxnode], rs[maxnode], sum[maxnode], cur, LL[30], RR[30];
#define mid (l + r >> 1)
#define lson ls[p], l, mid
#define rson rs[p], mid + 1, r
void update(int &p, int l, int r, int pos, int num)
{
if (!p) p = ++cur;
sum[p] += num;
if (l == r) return;
else if (pos <= mid) update(lson, pos, num);
else update(rson, pos, num);
}
int n, m, a[maxn], pos[maxn];
long long ans;
int query(int l, int r, int val, bool mode)
{
int lsz(0), rsz(0), s(0);
for (int i = l-1; i > 0; i -= i & -i) LL[++lsz] = rt[i];
for (int i = r ; i > 0; i -= i & -i) RR[++rsz] = rt[i];
l = 1, r = n;
while (l < r)
if (val > mid)
{
if (mode)
{
REP(i, 1, lsz) s -= sum[ls[LL[i]]];
REP(i, 1, rsz) s += sum[ls[RR[i]]];
}
REP(i, 1, lsz) LL[i] = rs[LL[i]];
REP(i, 1, rsz) RR[i] = rs[RR[i]];
l = mid + 1;
}
else
{
if (!mode)
{
REP(i, 1, lsz) s -= sum[rs[LL[i]]];
REP(i, 1, rsz) s += sum[rs[RR[i]]];
}
REP(i, 1, lsz) LL[i] = ls[LL[i]];
REP(i, 1, rsz) RR[i] = ls[RR[i]];
r = mid ;
}
return s;
}
int main()
{
#ifdef CraZYali
freopen("3157.in", "r", stdin);
freopen("3157.out", "w", stdout);
#endif
cin >> n >> m;
REP(i, 1, n)
{
pos[a[i] = read<int>()] = i;
ans += 1ll * query(1, i-1, a[i], 0);
for (int j = i; j <= n; j += j & -j) update(rt[j], 1, n, a[i], 1);
}
while (m --> 0)
{
printf("%lld\n", ans);
int x = read<int>(), p = pos[x];
ans -= query(1, p - 1, x, 0);
ans -= query(p + 1, n, x, 1);
for (int i = p; i <= n; i += i & -i) update(rt[i], 1, n, x, -1);
}
return 0;
}
|
