md 空间卡死窝了……
首先用常规方法求出这个序列的逆序对个数，然后每次删除就从答案中减去它对答案的贡献。
问题在于贡献怎么求。
显然，\(a_i\) 对答案的贡献就是 \(\sum\limits_{j = 1}^{i - 1}{[a_j > a_i]} + \sum\limits_{j = i + 1}^n{[a_j < a_i]}\)， 其中 \([X]\) 的意义是若 \(X\) 成立则为 \(1\) 否则为 \(0\)。
那么这个东西就用树套树就好啦！ 然后一开始的逆序对个数我也顺便用了树套树。
这里是树状数组套权值线段树。
代码： 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
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}
const int N = 1e5;
int n,m;
int a[N + 10],pos[N + 10];
int rt[N + 10];
long long ans;
struct node
{
int sz;
int lson,rson;
} seg[N * 100 + 10];
inline int new_node()
{
static int tot = 0;
return ++tot;
}
void insert(int x,int k,int &p,int tl,int tr)
{
if(!p)
p = new_node();
if(tl == tr)
{
seg[p].sz += k;
return ;
}
int mid = tl + tr >> 1;
if(x <= mid)
insert(x,k,ls(p),tl,mid);
else
insert(x,k,rs(p),mid + 1,tr);
seg[p].sz = seg[ls(p)].sz + seg[rs(p)].sz;
}
int ask(int l,int r,int p,int tl,int tr)
{
if(!p || l > r)
return 0;
if(l <= tl && tr <= r)
return seg[p].sz;
int mid = tl + tr >> 1;
int ret = 0;
if(l <= mid)
ret += ask(l,r,ls(p),tl,mid);
if(r > mid)
ret += ask(l,r,rs(p),mid + 1,tr);
return ret;
}
inline void update(int x,int v,int k)
{
for(;x <= n;x += lowbit(x))
insert(v,k,rt[x],1,n);
}
inline int query(int x,int v)
{
int ret = 0;
for(;x;x -= lowbit(x))
ret += ask(1,v,rt[x],1,n);
return ret;
}
int main()
{
read(n),read(m);
for(register int i = 1;i <= n;++i)
read(a[i]),update(i,a[i],1),pos[a[i]] = i;
for(register int i = 1;i <= n;++i)
ans += query(i - 1,n) - query(i - 1,a[i]);
int x;
while(m--)
{
read(x);
printf("%lld\n",ans);
ans -= (query(pos[x] - 1,n) - query(pos[x] - 1,x)) + (query(n,x - 1) - query(pos[x],x - 1));
update(pos[x],x,-1);
}
}