关键词:CDQ分治  主席树 相关题目:[CQOI2011]动态逆序对

题目描述

对于序列A,它的逆序对数定义为满足iAj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

输入输出格式

输入格式:

输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数,即初始排列。以下m行每行一个正整数,依次为每次删除的元素。

输出格式: 输出包含m行,依次为删除每个元素之前,逆序对的个数。

输入样例:

5 4
1
5
3
4
2
5
1
4
2

输出样例:

5
2
2
1

说明

N<=100000 M<=50000

Solution

解法:树状数组+主席树

先求出所有逆序对数。考虑每一个删除的数对当前所有数的贡献,发现为该数 前方大于该数后方小于该数 的数的个数。我们用主席树维护区间(前面和后面)满足条件数的个数。对于删除操作,直接删除 复杂度为 O(n)。于是用树状数组维护整体的主席树,树状数组的每一个节点 i 表示 第 i 棵主席树的根节点。

AC代码

树状数组+主席树

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
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int N = 100020;
inline int lowbit(int x) { return x&-x;}

int n, m;
long long ans=0;
int id = 0, w[N];
int root[85*N], ls[85*N], rs[85*N], siz[85*N];

inline void add(int &now, int l, int r, int z, int v) {
if(!now) now = ++id;
siz[now] += v;
if(l==r) return ;
int mid = (l+r)>>1;
if(z <= mid) add(ls[now], l, mid, z, v);
else add(rs[now], mid+1, r, z, v);
}

inline void modify(int d, int x, int v) {
for(re i=d; i<=n; i+=lowbit(i))
add(root[i], 1, n, x, v);
} //修改

int _l[N], _r[N], left, right;

inline long long query(int l, int r, int x, int b) {
if(l==r) return 0;
long long sum = 0;
int mid = (l+r)>>1;
if(b) {
if(x <= mid) {
rep(i,1,left) sum += siz[rs[_l[i]]];
rep(i,1,left) _l[i] = ls[_l[i]];
return sum + query(l, mid, x, b);
}
else {
rep(i,1,left) _l[i] = rs[_l[i]];
return query(mid+1, r, x, b);
}
} //section 1 前方大于
else {
if(x <= mid) {
rep(i,1,left) _l[i] = ls[_l[i]];
rep(i,1,right) _r[i] = ls[_r[i]];
return query(l, mid, x, b);
}
else {
rep(i,1,left) sum -= siz[ls[_l[i]]];
rep(i,1,right) sum += siz[ls[_r[i]]];
rep(i,1,left) _l[i] = rs[_l[i]];
rep(i,1,right) _r[i] = rs[_r[i]];
return sum + query(mid+1, r, x, b);
}
} //section 2 后方小于
} //查询

int main() {
scanf("%d%d", &n, &m);
int x;
rep(i,1,n) {
scanf("%d", &x), w[x]=i;
modify(i, x, 1);
for(re z=x; z<=n; z+=lowbit(z)) ++_l[z];
int res = 0;
for(re z=x; z; z-=lowbit(z)) res += _l[z];
ans += i-res;
}

int d;
while(m--) {
printf("%lld\n", ans);
scanf("%d", &d);

left = right = 0;
for(re i=w[d]-1; i; i-=lowbit(i)) _l[++left] = root[i];
ans -= query(1, n, d, 1);

left = right = 0;
for(re i=n; i; i-=lowbit(i)) _r[++right] = root[i];
for(re i=w[d]; i; i-=lowbit(i)) _l[++left] = root[i];
ans -= query(1, n, d, 0);

modify(w[d], d, -1);
}
}